ΘΕΩΡΙΑ ΔΥΑΔΙΚΟΥ ΔΕΝΤΡΟΥ ΑΝΑΖΗΤΗΣΕΩΣ ΜΕΡΟΣ ΔΕΥΤΕΡΟ

Προγραμματιστικά το δυαδικό δέντρο αναζητήσεως (binary search tree) υλοποιείται ως εξής:

public class BSTree
{
private BTNode root;     // Η ρίζα του δέντρου
private int size;     // Το πλήθος των κόμβων
boolean left=true;     // Ορισμός του αριστερού
boolean right=false;     // Ορισμός του δεξιού

public BSTree()
{
root=null;
size=0;
}

public int getSize()     // Επιστρέφει το μέγεθος του δέντρου
{
return size;
}

public void setSize(int a)
{
size=a;
}

public BTNode getRoot()     // Επιστρέφει τη ρίζα του δέντρου
{
return root;
}

public void setRoot(BTNode a)
{
root=a;
}

public boolean isRoot(BTNode a)     // Εξετάζει αν ο κόμβος a είναι η ρίζα
{
return (root==a);
}

public boolean isLeft(BTNode a)     // Εξετάζει αν ο κόμβος a είναι αριστερό παιδί
{
if (root==a)
{
System.out.println("Είσαι στη ρίζα");
return false;
}
return (a==a.getParent().getLeft());
}

public boolean isRight(BTNode a)     // Εξετάζει αν ο κόμβος a είναι δεξιό παιδί
{
if (root==a)
{
System.out.println("Είσαι στη ρίζα");
return false;
}
return (a==a.getParent().getRight());
}

public void exchangeElements(BTNode a, BTNode b)     // Ανταλλάσσει τα περιεχόμενα των κόμβων a και b
{
Object temp=a.getItem();
a.setItem(b.getItem());
b.setItem(temp);
}

public BTNode findNode(int key, BTNode a)     // Επιστρέφει τον κόμβο, εάν υπάρχει, που έχει
{                                                                             // αποθηκευμένο ένα Item με κλειδί key, το οποίο
int nodeKey=a.getItem().getKey();                      // θεωρούμε πως είναι int, περιορίζοντας την αναζήτηση στο υπόδεντρο                       

if (key < nodeKey)
{
if (a.getLeft()==null)
return a;
else
return findNode(key, a.getLeft());
}
else if (key==nodeKey)
return a;
else
{
if (a.getRight()==null)
return a;
else
return findNode(key, a.getRight());
}
}

public void addLeaf(BTNode a, boolean kindOfSon)
{
if (kindOfSon==left)     // Ένθεση αριστερού παιδιού
{
if (a.getLeft()!=null)     // Υπάρχει ήδη μη κενό αριστερό παιδί
{
System.out.println("Υπάρχει τέτοιο παιδί!");
return;
}

a.setLeft(new BTNode(null, a, null, null));     // Ένθεση του νέου κόμβου
}
else     // Αιτείται ένθεση δεξιού παιδιού
{
if (a.getRight()!=null)     // Υπάρχει τέτοιο παιδί
{
System.out.println("Υπάρχει τέτοιο παιδί!");
return;
}

a.setRight(new BTNode(null, a, null, null));     // Ένθεση του νέου κόμβου
}
size++;     // Ενημέρωση του μεγέθους του δέντρου

}

public void deleteNode(BTNode a)
{
if ((a.getLeft()!=null)&&(a.getRight()!=null))     // Αδύνατη η απόσβεση διότι και τα δύο παιδιά υπάρχουν
{
System.out.println("Η διαγραφή είναι αδύνατη!");
return;
}

if (isRoot(a))
{
BTNode notNullSon=(a.getLeft() != null ? a.getLeft() : a.getRight());
root=notNullSon;     // Θα γίνει η νέα ρίζα

if (root != null)     // Οπότε δεν έχει πατέρα
root.setParent(null);
}
else     // Δεν είναι ρίζα
{
BTNode parentOfa=a.getParent();     // Οπότε έχει πατέρα
BTNode notNullSon=(a.getLeft() != null ? a.getLeft() : a.getRight());

if (isLeft(a))
parentOfa.setLeft(notNullSon);
else
parentOfa.setRight(notNullSon);

if (notNullSon!=null)
notNullSon.setParent(parentOfa);     // Αλλαγή πατρός
}
size--;     // Ενημέρωση μεγέθους του δέντρου
a.setLeft(null);
a.setRight(null);
a.setParent(null);
}

public BTNode insertItem(Item i)     // Ενθέτει ένα νέο Item στο δέντρο, επιστρέφοντας τον BTNode που     
{                                                          // το αποθηκεύει, εφόσον δεν υπάρχει άλλο Item με ίδιο
if (size==0)                                         // κλειδί. Εάν υπάρχει δεν κάνει τίποτα και επιστρέφει null
{                                                          
setRoot(new BTNode(i, null, null, null);
setSize(1);
return root;
}

BTNode insNode=findNode(i.getKey(), getRoot());     // Η αναζήτηση βάσει κλειδιού
int keyNode=insNode.getItem().getKey();     // Κλειδί του κόμβου

if (keyNode==i.getKey())     // Υπάρχει ήδη τέτοιο κλειδί
return null;
else     // Δεν υπάρχει, οπότε θα τοποθετηθεί είτε ως αριστερό είτε ως δεξιό παιδί
{
if (i.getKey() < keyNode)     // Είναι μικρότερο, πρέπει να μπει αριστερά
{
addLeaf(insNode, left);
insNode.getLeft().setItem(i);
return insNode.getLeft();
}
else     // Είναι μεγαλύτερο, πρέπει να μπει δεξιά 
{
addLeaf(insNode, right);
insNode.getRight().setElement(i);
return insNode.getRight();
}
}
}

public BTNode deleteItem(int key)     // Διαγράφεται, εφόσον υπάρχει τέτοιο, το Item του δέντρου        
{                                                            // με κλειδί key, επιστρέφοντας τον εναπομείναντα εμπλεκόμενο
if (size==0)                                           // κόμβο. Εάν δεν υπάρχει, δεν κάνει τίποτα επιστρέφοντας null
return null;                                          

BTNode delNode=findNode(key, getRoot());     // Αναζήτηση βάσει κλειδιού
int keyNode=delNode.getItem().getKey();     // Το κλειδί του κόμβου

if (keyNode!=key)     // Δεν υπάρχει τέτοιο Item
return null;

else     // Υπάρχει τέτοιο Item
{
BTNode returnNode;

if ((delNode.getLeft()==null)||(delNode.getRight()==null))     // Έχει γιο null
{
returnNode=(delNode.getLeft() != null ? delNode.getLeft() : delNode.getRight() != null ? delNode.getRight() : delNode.getParent());
deleteNode(delNode);
return returnNode;
}
else     // Και τα δύο του παιδιά είναι κανονικοί κόμβοι, οπότε πρέπει να βρούμε τον κόμβο του αριστερού υπόδεντρου με το μικρότερο κλειδί
{
BTNode cursor=delNode.getRight();
BTNode temp;
BTNode parentDelNode;

while ((temp =cursor.getLeft())!=null)
cursor=temp;

exchangeElements(cursor, delNode);     // Ανταλλαγή περιεχομένων
parentDelNode=cursor.getParent();
deleteNode(cursor);
return parentDelNode;
}
}

}     // Τέλος BSTree