Στα δυαδικά δέντρα αναζητήσεως (binary search trees) ισχύει η κάτωθι αμετάβλητη συνθήκη:
Το κλειδί του αριστερού γιου του κόμβου u είναι μικρότερο από αυτό του u ενώ ο δεξιός γιος του u διαθέτει μεγαλύτερο κλειδί από εκείνο του u.
Ως δομικό στοιχείο του δέντρου, μεταχειριζόμαστε έναν κόμβο BTNode, ο οποίος θα φέρει το στοιχείο Item και τρεις δείκτες, τον parent προς τον πατέρα και τους left, right προς το αριστερό και δεξιό παιδί, αντίστοιχα. Στην παρακάτω εικόνα φαίνεται ο κόμβος BTNode:
Προγραμματιστικά ο κόμβος του δυαδικού δέντρου BTNode ορίζεται ως εξής:
public class BTNode
{
private Item element;
private BTNode left, right, parent;
public BTNode(Item element, BTNode parent, BTNode left, BTNode right) // Σύνθετος κατασκευαστής με πλήρη καθορισμό των περιεχομένων του νέου κόμβου
{
this.element=element;
this.parent=parent;
this.left=left;
this.right=right;
}
public void setItem(Item a) // Θέτει το αποθηκευμένο στοιχείο
{
element=a;
}
public Item getItem() // Επιστρέφει το στοιχείο
{
return element;
}
public void setParent(BTNode a) // Θέτει τον δείκτη προς τον πατέρα
{
parent=a;
}
public BTNode getParent() // Επιστρέφει τον δείκτη προς τον πατέρα
{
return parent;
}
public void setLeft(BTNode a) // Θέτει τον δείκτη προς το αριστερό παιδί
{
left=a;
}
public BTNode getLeft() // Επιστρέφει τον δείκτη προς το αριστερό παιδί
{
return left;
}
public void setRight(BTNode a) // Θέτει τον δείκτη προς το δεξιό παιδί
{
right=a;
}
public BTNode getRight() // Επιστρέφει τον δείκτη προς το δεξιό παιδί
{
return right;
}
} // Τέλος BTNode
Εισαγωγή στοιχείου: Η εισαγωγή ενός νέου στοιχείου σε δυαδικό δέντρο αναζητήσεως περιλαμβάνει μία αναζήτηση βάσει του κλειδιού. Εάν το δέντρο διαθέτει ήδη αντικείμενο με αυτό το κλειδί τότε η διαδικασία σταματά. Διαφορετικά, τοποθετείται στη θέση του κατάλληλου κενού φύλλου του κόμβου που επιστρέφει η διαδικασία ψαξίματος. Στο παρακάτω σχήμα φαίνεται η εισαγωγή 12 κόμβων σε ένα αρχικά άδειο δέντρο αναζητήσεως. Με έντονο χρώμα εικονίζονται τα μονοπάτια αναζητήσεως, δηλαδή οι δείκτες που ακολουθούν οι αντίστοιχες διαδικασίες αναζητήσεως προκειμένου να εντοπιστούν οι θέσεις τοποθετήσεως των νέων κόμβων. Για παράδειγμα, η εισαγωγή του 18 προκαλεί αναζήτηση που καταλήγει στην άκρα δεξιά κόμβο με κλειδί 20. Κατόπιν, δημιουργείται ένας νέος κόμβος, αριστερό παιδί του 20, ώστε να στεγάσει το στοιχείο με τιμή κλειδιού 18. Παρακάτω φαίνεται το σχήμα:
Διαγραφή στοιχείου: Η διαγραφή ενός στοιχείου είναι ελάχιστα δυσκολότερη. Περιλαμβάνει και αυτή μία αναζήτηση βάσει του κλειδιού. Εάν το δέντρο δε διαθέτει ανικείμενο με το κλειδί για παράδειγμα x, τότε η διαδικασία σταματά. Διαφορετικά, έστω delNode το Item. Διακρίνουμε δύο περιπτώσεις:
Εάν ο delNode διαθέτει τουλάχιστον ένα κενό φύλλο, προκειμένου να διατηρηθεί η αμετάβλητη συνθήκη που διέπει το δέντρο, καταργείται ο delNode και το δεύτερο, ενδεχομένως μη κενό, παιδί του u συνδέεται με τον πατέρα p του delNode.
Διαφορετικά, ο delNode διαθέτει μη κενό δεξιό γιο q. Οπότε ανταλλάσσουμε το στοιχείο Item του delNode με αυτό του βαθύτερου, αριστερότερου μη κενού απόγονου w του δεξιού υποδένδρου. Κατά αυτόν τον τρόπο, είναι σαν οι w και delNode να άλλαξαν θέσεις! Οπότε δημιουργούνται οι συνθήκες της πρώτης περίπτωσης, η οποία και εφαρμόζεται, ώστε ο delNode να διαγραφεί, δίχως παραβίαση της αμετάβλητης συνθήκης.
Στο παρακάτω σχήμα έχουμε 6 διαδοχικές διαγραφές στο δέντρο. Οι αποσβέσεις είναι των κόμβων είναι με τα κλειδιά 6, 9, 14, 4, 5, 20. Το σχήμα είναι το εξής:
