4. DB Praktikum und 2. ALG Praktikum

Hier zwei Lösungen für das vierte Datenbank Praktikum und das zweite Algorithmik Praktikum.

Das vierte Datenbank Praktikum handelte über die Erstellung einer Datenbank heraus aus einem ERM-Diagramm. Mittels dem Modellierungstool ERwin wurde der dazu nötige SQL-Code erstellt. Desweiteren wurden weitere SQL-Skripte für die restlichen Aufgabenteile erstellt. Dort sollten dann Benutzerrechte gesetzt , Constraints hinzugefügt und als Test in jede Tabelle mindestens eine Zeile eingefügt werden.

Create: CREATE

Constraints: ALTER

Insert: INSERT

Im zweiten Algorithmik Praktikum wurden AVL-Bäume behandelt. Aufgabe war es ein einfaches Konsolen-Interface zu programmieren, welches die entsprechenden Operationen für AVL-Bäume anspricht. Die Operationen mussten selbstverständlich auch programmiert werden.

AVLNode.java:

public class AVLNode{
protected AVLNode left;
protected AVLNode right;
protected int balance;
public int value;

//Konstruktoren

 public AVLNode(int value){
this(value, null, null);
}

 public AVLNode(int value, AVLNode left, AVLNode right){
this.value=value;
this.left=left;
this.right=right;
balance=0;
}

/**
* Liefert die Höhe eines Teilbaumes
* @return Gibt die Höhe eines Teilbaumes zurück
*/

 public int hoehe(){
int l=0;
int r=0;

if(left!=null) l=left.hoehe();
if(right!=null) r=right.hoehe();
return Math.max(l, r)+1;
}
}

AVLTree.java:

public class AVLTree{

private AVLNode root;

/**
* Konstruktor
*/

 public AVLTree(){
root = null;
}

/**
* Aufruf um einen Knoten hinzu zu fügen
* @param value hinzu zu fügender Knoten
*/

public void insert(int value){
root = insert(value, root);
}

/**
* Aufruf um einen Knoten zu löschen
* @param value zu löschender Knoten
*/

public void remove(int value){
if(isEmpty()){
System.out.println(“Leerer Baum”);
}
else{
root = remove(value, root);
}
}

/**
* Löscht den kompletten Baum
*/

public void delete(){
root = null;
}

/**
* Prüft ob der Baum leer ist
* @return true oder false
*/

 public boolean isEmpty(){
return root==null;
}

/**
* Aufruf der versetzten Ausgabe
*/

 public void ausgBinaerBaum(){
if(isEmpty()){
System.out.println(“Leerer Baum”);
}
else{
ausgBinaerBaum(root,0);
}
}
//——————————————————————
/**
* Gibt den Baum ab dem angegebenen Knoten versetzt aus
*/

 public void ausgBinaerBaum(AVLNode node, int step){
if(node != null){
ausgBinaerBaum(node.right, step + 1);
for (int i=0; i < step; i++){
System.out.print(“-“);
}
System.out.println(node.value+”  (“+node.balance+”)”);
ausgBinaerBaum(node.left, step + 1);
}
}

/**
* Berechnet die Balance des jeweiligen Knotens
*/

private static int bal(AVLNode p){
AVLNode r=p.right;
AVLNode l=p.left;
int bal=0;

if(r!=null && l!=null){
bal=r.hoehe()-l.hoehe();
}
else if(r!=null && l==null){
bal=r.hoehe();
}
else if(r==null && l!=null){
bal=0-l.hoehe();
}
return bal;
}

/**
* Fügt einen Knoten in den angegebenen Teilbaum ein
*/

private AVLNode insert(int value, AVLNode node){
if(node == null){
node = new AVLNode(value, null, null);
}
else if (value < node.value){
node.left = insert(value, node.left);
node=upin(node);
}
else if(value > node.value){
node.right = insert(value, node.right);
node=upin(node);
}
else{
System.out.println(“Der Knoten ist schon vorhanden!”);
}
return node;
}

private AVLNode upin(AVLNode node){
node.balance=bal(node);
if(node.balance==-2){
if(node.left.balance!=1){
node = rotationRight(node);
}
else{
node = doublerotationLeftRight(node);
}
}
else if(node.balance==2){
if(node.right.balance!=-1){
node = rotationLeft(node);
}
else{
node = doublerotationRightLeft(node);
}
}
return node;
}

//Rechtsrotation

 private static AVLNode rotationRight(AVLNode node){
AVLNode temp = node.left;
node.left = temp.right;
temp.right = node;

node.balance = bal(node);
temp.balance = bal(node);

return temp;
}

//doppelt: Links-Rechts-Rotation

 private static AVLNode doublerotationLeftRight(AVLNode node){
node.left = rotationLeft(node.left);
return rotationRight(node);
}

//Linksrotation

 private static AVLNode rotationLeft(AVLNode node){
AVLNode temp = node.right;
node.right = temp.left;
temp.left = node;

node.balance = bal(node);
temp.balance = bal(node);

return temp;
}

//doppelt: Rechts-Links-Rotation

 private static AVLNode doublerotationRightLeft(AVLNode node){
node.right = rotationRight(node.right);
return rotationLeft(node);
}

/**
* Entfernt einen Knoten aus dem angegebenen Teilbaum
*/

 private AVLNode remove(int value, AVLNode node){
if(node == null){
System.out.println(“Wert nicht vorhanden”);
}
else if (value == node.value){
if(node.left == null){
return node.right;
}
else if(node.right == null){
return node.left;
}
else{
if(node==root){
node=rootRemove(node);
return node;
}
else{
AVLNode temp=Successor(node);
remove(temp.value, node);
node.value=temp.value;
return node;
}
}
}
else if (value < node.value){
node.left = remove(value, node.left);
node=upout(node);
}
else if(value > node.value){
node.right = remove(value, node.right);
node=upout(node);
}
return node;
}

 private AVLNode rootRemove(AVLNode node){
AVLNode prev=null;
AVLNode temp=node.right;
while(temp.left != null){
prev=temp;
temp=temp.left;
}
if(prev!=null){
prev.left=temp.right;
temp.right=node.right;
prev.balance=bal(prev);
}
temp.left=node.left;
node=temp;
if(node.right!=null){
node.right=upout(node.right);
}
node=upout(node);
return node;
}

 private AVLNode upout(AVLNode node){
node.balance=bal(node);
if(node.balance==2){
if(node.right.balance!=-1){
node = rotationLeft(node);
}
else{
node = doublerotationRightLeft(node);
}
}
else if(node.balance==-2){
if(node.left.balance!=1){
node = rotationRight(node);
}
else{
node = doublerotationLeftRight(node);
}
}
node.balance=bal(node);
return node;
}

 private AVLNode Successor(AVLNode node){
AVLNode temp=node.right;
while(temp.left != null){
temp=temp.left;
}
return temp;
}

private AVLNode Predecessor(AVLNode node){
AVLNode temp=node.left;
while(temp.right != null){
temp=temp.right;
}
return temp;
}

 public boolean IsSuccessor(int node, int node2){
AVLNode temp=IsMember(node2);
AVLNode temp2=Successor(temp);
if(temp2.value==node){
return true;
}
return false;
}

public boolean IsPredecessor(int node, int node2){
AVLNode temp=IsMember(node2);
AVLNode temp2=Predecessor(temp);
if(temp2.value==node){
return true;
}
return false;
}

public AVLNode IsMember(int value){
AVLNode node = root;
while(node != null){
if(value == node.value){
return node;
}
else if(value<node.value){
node = node.left;
}
else{
node = node.right;
}
}
return null;
}
}

Main.java:

import java.util.Scanner;

public class Main{
public static void main(String[] args){

boolean fertig = true;
Scanner scan = new Scanner(System.in);
AVLTree Baum = new AVLTree();

while(fertig){
System.out.println(“———————————————————“);
System.out.println(“1   –  Knoten hinzufuegen || 2   –  Knoten löschen”);
System.out.println(“3   –  AVL-Baum löschen   || 4   –  Suchen”);
System.out.println(“5   –  IsPredecessor      || 6   – IsSuccessor”);
System.out.println(“9   –  Beenden”);
System.out.println(“———————————————————“);
if(!Baum.isEmpty()){
System.out.println(“****************************************”);
Baum.ausgBinaerBaum();
System.out.println(“****************************************”);
}
//Auswahl einlesen
int Zahl = scan.nextInt();

//Menüoptionen
  switch(Zahl){
case 1:
int wert = scan.nextInt();
Baum.insert(wert);
break;
case 2:
int wert2 = scan.nextInt();
Baum.remove(wert2);
break;
case 3:
     Baum.delete();
break;
case 4:
int wert3 = scan.nextInt();
AVLNode temp=Baum.IsMember(wert3);
if(temp!=null&&temp.value==wert3){
System.out.println(wert3+” ist vorhanden!”);
}
else{
System.out.println(wert3+” ist nicht vorhanden!”);
}
break;
  case 5:
if(!Baum.isEmpty()){
System.out.println(“Geben Sie den Vorgängerknoten an den Sie vergleichen wollen:”);
int wert4 = scan.nextInt();
System.out.println(“Geben Sie Knoten an dessen Vorgänger mit ihrem angegebenen Vorgänger verglichen werden soll:”);
int wert5 = scan.nextInt();
if(Baum.IsPredecessor(wert4, wert5)==true){
System.out.println(wert4+” ist der Vorgänger von “+wert5+”!”);
}
else{
System.out.println(wert4+” ist nicht der Vorgänger von “+wert5+”!”);
}
}
else{
System.out.println(“Leerer Baum”);
}
break;
 case 6:
if(!Baum.isEmpty()){
System.out.println(“Geben Sie den Nachfolgerknoten an den Sie vergleichen wollen:”);
int wert6 = scan.nextInt();
System.out.println(“Geben Sie Knoten an dessen Nachfolger mit ihrem angegebenen Nachfolger verglichen werden soll:”);
int wert7 = scan.nextInt();
if(Baum.IsSuccessor(wert6, wert7)==true){
System.out.println(wert6+” ist der Nachfolger von “+wert7+”!”);
}
else{
System.out.println(wert6+” ist nicht der Nachfolger von “+wert7+”!”);
}
}
else{
System.out.println(“Leerer Baum”);
}
break;
case 9:
fertig = false;
}
}
}
}