Δυαδικά δέντρα αναζήτησης: Το BST εξηγείται με παραδείγματα

Τι είναι το Δυαδικό Δέντρο Αναζήτησης;

Ένα δέντρο είναι μια δομή δεδομένων που αποτελείται από κόμβους που έχουν τα ακόλουθα χαρακτηριστικά:

  1. Κάθε δέντρο έχει έναν ριζικό κόμβο στην κορυφή (επίσης γνωστός ως Γονικός κόμβος) που περιέχει κάποια τιμή (μπορεί να είναι οποιοσδήποτε τύπος δεδομένων).
  2. Ο ριζικός κόμβος έχει μηδέν ή περισσότερους θυγατρικούς κόμβους.
  3. Κάθε θυγατρικός κόμβος έχει μηδέν ή περισσότερους θυγατρικούς κόμβους και ούτω καθεξής. Αυτό δημιουργεί ένα υποδένδρο στο δέντρο. Κάθε κόμβος έχει το δικό του υπόστρωμα που αποτελείται από τα παιδιά του και τα παιδιά τους, κ.λπ. Αυτό σημαίνει ότι κάθε κόμβος από μόνος του μπορεί να είναι δέντρο.

Ένα δέντρο δυαδικής αναζήτησης (BST) προσθέτει αυτά τα δύο χαρακτηριστικά:

  1. Κάθε κόμβος έχει έως και δύο παιδιά.
  2. Για κάθε κόμβο, οι τιμές των κόμβων του αριστερού απογόνου είναι μικρότερες από εκείνες του τρέχοντος κόμβου, ο οποίος με τη σειρά του είναι μικρότερος από τους κόμβους του δεξιού απογόνου (εάν υπάρχουν).

Το BST βασίζεται στην ιδέα του αλγορίθμου δυαδικής αναζήτησης, ο οποίος επιτρέπει γρήγορη αναζήτηση, εισαγωγή και αφαίρεση κόμβων. Ο τρόπος με τον οποίο ρυθμίζονται σημαίνει ότι, κατά μέσο όρο, κάθε σύγκριση επιτρέπει στις λειτουργίες να παραλείψουν περίπου το μισό του δέντρου, έτσι ώστε κάθε αναζήτηση, εισαγωγή ή διαγραφή να πάρει χρόνο ανάλογο με τον λογάριθμο του αριθμού των αντικειμένων που είναι αποθηκευμένα στο δέντρο,   O(log n). Ωστόσο, μερικές φορές η χειρότερη περίπτωση μπορεί να συμβεί, όταν το δέντρο δεν είναι ισορροπημένο και η πολυπλοκότητα του χρόνου είναι και   O(n)  για τις τρεις αυτές λειτουργίες. Αυτός είναι ο λόγος για τον οποίο τα δέντρα αυτοεξισορρόπησης (AVL, κόκκινο-μαύρο κ.λπ.) είναι πολύ πιο αποτελεσματικά από το βασικό BST.

Παράδειγμα χειρότερης περίπτωσης:  Αυτό μπορεί να συμβεί όταν συνεχίζετε να προσθέτετε κόμβους που είναι   πάντα  μεγαλύτεροι από τον κόμβο πριν (ο γονέας του), το ίδιο μπορεί να συμβεί όταν προσθέτετε πάντα κόμβους με τιμές χαμηλότερες από τους γονείς τους.

Βασικές λειτουργίες σε BST

  • Δημιουργία: δημιουργεί ένα κενό δέντρο.
  • Εισαγωγή: εισαγάγετε έναν κόμβο στο δέντρο.
  • Αναζήτηση: Αναζητά έναν κόμβο στο δέντρο.
  • Διαγραφή: διαγράφει έναν κόμβο από το δέντρο.
  • Inorder: εγκάρσια διατομή του δέντρου.
  • Προπαραγγελία: προπαραγγελία διέλευσης του δέντρου.
  • Postorder: μετά την παραγγελία διασταύρωση του δέντρου.

Δημιουργώ

Αρχικά δημιουργείται ένα κενό δέντρο χωρίς κόμβους. Η μεταβλητή / αναγνωριστικό που πρέπει να δείχνει στον ριζικό κόμβο αρχικοποιείται με μια   NULL  τιμή.

Αναζήτηση

Ξεκινάτε πάντα την αναζήτηση του δέντρου στον ριζικό κόμβο και κατεβαίνετε από εκεί. Συγκρίνετε τα δεδομένα σε κάθε κόμβο με αυτόν που αναζητάτε. Εάν ο συγκρινόμενος κόμβος δεν ταιριάζει, τότε είτε προχωράτε στο δεξί παιδί είτε στο αριστερό παιδί, το οποίο εξαρτάται από το αποτέλεσμα της ακόλουθης σύγκρισης: Εάν ο κόμβος που αναζητάτε είναι χαμηλότερος από αυτόν που συγκρίνατε, προχωράτε στο αριστερό παιδί, διαφορετικά (εάν είναι μεγαλύτερο) πηγαίνετε στο δεξί παιδί. Γιατί; Επειδή το BST είναι δομημένο (σύμφωνα με τον ορισμό του), ότι το δεξί παιδί είναι πάντα μεγαλύτερο από τον γονέα και το αριστερό παιδί είναι πάντα μικρότερο.

Πρώτη αναζήτηση (BFS)

Η πρώτη αναζήτηση εύρους είναι ένας αλγόριθμος που χρησιμοποιείται για να διασχίσει ένα BST. Ξεκινά στον ριζικό κόμβο και ταξιδεύει με πλευρικό τρόπο (πλάι-πλάι), αναζητώντας τον επιθυμητό κόμβο. Αυτός ο τύπος αναζήτησης μπορεί να περιγραφεί ως O (n) δεδομένου ότι κάθε κόμβος επισκέπτεται μία φορά και το μέγεθος του δέντρου σχετίζεται άμεσα με το μήκος της αναζήτησης.

Αναζήτηση πρώτου βάθους (DFS)

Με μια προσέγγιση αναζήτησης πρώτου βάθους, ξεκινάμε με τον ριζικό κόμβο και ταξιδεύουμε σε έναν κλάδο. Εάν ο επιθυμητός κόμβος βρίσκεται κατά μήκος αυτού του κλάδου, θαυμάσιος, αλλά εάν όχι, συνεχίστε προς τα πάνω και αναζητήστε μη επισκέψιμους κόμβους. Αυτός ο τύπος αναζήτησης έχει επίσης μια μεγάλη σημείωση O του O (n).

Εισάγετε

Είναι πολύ παρόμοιο με τη λειτουργία αναζήτησης. Ξεκινάτε ξανά από τη ρίζα του δέντρου και κατεβαίνετε αναδρομικά, αναζητώντας το σωστό μέρος για να εισαγάγετε τον νέο μας κόμβο, με τον ίδιο τρόπο όπως εξηγείται στη λειτουργία αναζήτησης. Εάν ένας κόμβος με την ίδια τιμή υπάρχει ήδη στο δέντρο, μπορείτε να επιλέξετε είτε να εισαγάγετε το αντίγραφο είτε όχι. Μερικά δέντρα επιτρέπουν διπλότυπα, κάποια όχι. Εξαρτάται από τη συγκεκριμένη εφαρμογή.

Διαγραφή

Υπάρχουν 3 περιπτώσεις που μπορούν να συμβούν όταν προσπαθείτε να διαγράψετε έναν κόμβο. Εάν έχει,

  1. Χωρίς υποδένδρο (χωρίς παιδιά): Αυτό είναι το πιο εύκολο. Μπορείτε απλά να διαγράψετε τον κόμβο, χωρίς να απαιτούνται πρόσθετες ενέργειες.
  2. Ένα δευτερεύον δέντρο (ένα παιδί): Πρέπει να βεβαιωθείτε ότι μετά τη διαγραφή του κόμβου, το παιδί του συνδέεται στη συνέχεια με τον γονέα του διαγραμμένου κόμβου.
  3. Two subtrees (two children): You have to find and replace the node you want to delete with its inorder successor (the leftmost node in the right subtree).

The time complexity for creating a tree is  O(1) . The time complexity for searching, inserting or deleting a node depends on the height of the tree  h , so the worst case is  O(h)  in case of skewed trees.

Predecessor of a node

Predecessors can be described as the node that would come right before the node you are currently at. To find the predecessor of the current node, look at the right-most/largest leaf node in the left subtree.

Successor of a node

Successors can be described as the node that would come right after the the current node. To find the successor of the current node, look at the left-most/smallest leaf node in the right subtree.

Special types of BT

  • Heap
  • Red-black tree
  • B-tree
  • Splay tree
  • N-ary tree
  • Trie (Radix tree)

Runtime

Data structure: BST

  • Worst-case performance:  O(n)
  • Best-case performance:  O(1)
  • Average performance:  O(log n)
  • Worst-case space complexity:  O(1)

Where  n  is the number of nodes in the BST. Worst case is O(n) since BST can be unbalanced.

Implementation of BST

Here's a definition for a BST node having some data, referencing to its left and right child nodes.

struct node { int data; struct node *leftChild; struct node *rightChild; }; 

Search Operation

Whenever an element is to be searched, start searching from the root node. Then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree. Follow the same algorithm for each node.

struct node* search(int data){ struct node *current = root; printf("Visiting elements: "); while(current->data != data){ if(current != NULL) { printf("%d ",current->data); //go to left tree if(current->data > data){ current = current->leftChild; }//else go to right tree else { current = current->rightChild; } //not found if(current == NULL){ return NULL; } } } return current; } 

Insert Operation

Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

void insert(int data) { struct node *tempNode = (struct node*) malloc(sizeof(struct node)); struct node *current; struct node *parent; tempNode->data = data; tempNode->leftChild = NULL; tempNode->rightChild = NULL; //if tree is empty if(root == NULL) { root = tempNode; } else { current = root; parent = NULL; while(1) { parent = current; //go to left of the tree if(data data) { current = current->leftChild; //insert to the left if(current == NULL) { parent->leftChild = tempNode; return; } }//go to right of the tree else { current = current->rightChild; //insert to the right if(current == NULL) { parent->rightChild = tempNode; return; } } } } } 

Delete Operation

void deleteNode(struct node* root, int data){ if (root == NULL) root=tempnode; if (data key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); else { if (root->left == NULL) { struct node *temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct node *temp = root->left; free(root); return temp; } struct node* temp = minValueNode(root->right); root->key = temp->key; root->right = deleteNode(root->right, temp->key); } return root; } 

Binary search trees (BSTs) also give us quick access to predecessors and successors. Predecessors can be described as the node that would come right before the node you are currently at.

  • To find the predecessor of the current node, look at the rightmost/largest leaf node in the left subtree. Successors can be described as the node that would come right after the node you are currently at.
  • To find the successor of the current node, look at the leftmost/smallest leaf node in the right subtree.

Let's look at a couple of procedures operating on trees.

Since trees are recursively defined, it's very common to write routines that operate on trees that are themselves recursive.

So for instance, if we want to calculate the height of a tree, that is the height of a root node, We can go ahead and recursively do that, going through the tree. So we can say:

  • For instance, if we have a nil tree, then its height is a 0.
  • Otherwise, We're 1 plus the maximum of the left child tree and the right child tree.
  • So if we look at a leaf for example, that height would be 1 because the height of the left child is nil, is 0, and the height of the nil right child is also 0. So the max of that is 0, then 1 plus 0.

Height(tree) algorithm

if tree = nil: return 0 return 1 + Max(Height(tree.left),Height(tree.right)) 

Here is the code in C++

int maxDepth(struct node* node) { if (node==NULL) return 0; else { int rDepth = maxDepth(node->right); int lDepth = maxDepth(node->left); if (lDepth > rDepth) { return(lDepth+1); } else { return(rDepth+1); } } } 

We could also look at calculating the size of a tree that is the number of nodes.

  • Again, if we have a nil tree, we have zero nodes.
  • Otherwise, we have the number of nodes in the left child plus 1 for ourselves plus the number of nodes in the right child. So 1 plus the size of the left tree plus the size of the right tree.

Size(tree) algorithm

if tree = nil return 0 return 1 + Size(tree.left) + Size(tree.right) 

Here is the code in C++

int treeSize(struct node* node) { if (node==NULL) return 0; else return 1+(treeSize(node->left) + treeSize(node->right)); } 

Traversal

There are 3 kinds of traversals that are done typically over a binary search tree. All these traversals have a somewhat common way of going over the nodes of the tree.

In-order

This traversal first goes over the left subtree of the root node, then accesses the current node, followed by the right subtree of the current node. The code represents the base case too, which says that an empty tree is also a binary search tree.

void inOrder(struct node* root) { // Base case if (root == null) { return; } // Travel the left sub-tree first. inOrder(root.left); // Print the current node value printf("%d ", root.data); // Travel the right sub-tree next. inOrder(root.right); } 

Pre-order

This traversal first accesses the current node value, then traverses the left and right sub-trees respectively.

void preOrder(struct node* root) { if (root == null) { return; } // Print the current node value printf("%d ", root.data); // Travel the left sub-tree first. preOrder(root.left); // Travel the right sub-tree next. preOrder(root.right); } 

Post-order

This traversal puts the root value at last, and goes over the left and right sub-trees first. The relative order of the left and right sub-trees remain the same. Only the position of the root changes in all the above mentioned traversals.

void postOrder(struct node* root) { if (root == null) { return; } // Travel the left sub-tree first. postOrder(root.left); // Travel the right sub-tree next. postOrder(root.right); // Print the current node value printf("%d ", root.data); } 

Relevant videos on freeCodeCamp YouTube channel

And Binary Search Tree: Traversal and Height

Following are common types of Binary Trees:

Full Binary Tree/Strict Binary Tree: A Binary Tree is full or strict if every node has exactly 0 or 2 children.

 18 / \ / \ 15 30 / \ / \ 40 50 100 40 

In Full Binary Tree, number of leaf nodes is equal to number of internal nodes plus one.

Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

 18 / \ / \ 15 30 / \ / \ 40 50 100 40 / \ / 8 7 9 

Perfect Binary Tree A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level.

 18 / \ / \ 15 30 / \ / \ 40 50 100 40 

Augmenting a BST

Sometimes we need to store some additional information with the traditional data structures to make our tasks easier. For example, consider a scenario where you are supposed to find the ith smallest number in a set. You can use brute force here but we can reduce the complexity of the problem to O(lg n) by augmenting a red-black or any self-balancing tree (where n is the number of elements in the set). We can also compute rank of any element in O(lg n) time. Let us consider a case where we are augmenting a red-black tree to store the additional information needed. Besides the usual attributes, we can store number of internal nodes in the subtree rooted at x(size of the subtree rooted at x including the node itself). Let x be any arbitrary node of a tree.

x.size = x.left.size + x.right.size + 1

Ενώ αυξάνουμε το δέντρο, πρέπει να έχουμε κατά νου, ότι πρέπει να είμαστε σε θέση να διατηρούμε τις επαυξημένες πληροφορίες καθώς και να κάνουμε άλλες λειτουργίες όπως εισαγωγή, διαγραφή, ενημέρωση O(lg n)εγκαίρως.

Από τότε, γνωρίζουμε ότι η τιμή του x.left.size θα μας δώσει τον αριθμό των κόμβων που προχωρούν x με τη σειρά που διασχίζει το δέντρο. Έτσι, x.left.size + 1είναι η κατάταξη του x εντός του υποδέντρου με ρίζες στο x.