Дървета за бинарно търсене: BST, обяснено с примери

Какво е бинарно дърво за търсене?

Дървото е структура от данни, съставена от възли, която има следните характеристики:

  1. Всяко дърво има корен възел в горната част (известен също като родителски възел), съдържащ някаква стойност (може да бъде всеки тип данни).
  2. Коренният възел има нула или повече дъщерни възли.
  3. Всеки дъщерен възел има нула или повече дъщерни възли и т.н. Това създава поддърво в дървото. Всеки възел има свое собствено поддърво, съставено от своите деца и техните деца и т.н. Това означава, че всеки възел сам по себе си може да бъде дърво.

Двоично дърво за търсене (BST) добавя следните две характеристики:

  1. Всеки възел има максимум до две деца.
  2. За всеки възел стойностите на неговите леви низходящи възли са по-малки от тези на текущия възел, което от своя страна е по-малко от десните низходящи възли (ако има такива).

BST е изграден върху идеята за бинарния алгоритъм за търсене, който позволява бързо търсене, вмъкване и премахване на възли. Начинът, по който са настроени, означава, че средно всяко сравнение позволява на операциите да пропуснат около половината от дървото, така че всяко търсене, вмъкване или изтриване отнема време, пропорционално на логаритъма на броя на елементите, съхранявани в дървото,   O(log n). Въпреки това, понякога може да се случи най-лошият случай, когато дървото не е балансирано и сложността във времето е и   O(n)  за трите от тези функции. Ето защо самобалансиращите дървета (AVL, червено-черни и т.н.) са много по-ефективни от базовия BST.

Пример за най-лошия случай:  Това може да се случи, когато продължавате да добавяте възли, които винаги са    по-големи от възела преди (неговия родител), същото може да се случи, когато винаги добавяте възли със стойности, по-ниски от техните родители.

Основни операции на BST

  • Създаване: създава празно дърво.
  • Вмъкване: вмъкнете възел в дървото.
  • Търсене: Търси възел в дървото.
  • Изтриване: изтрива възел от дървото.
  • Inorder: обхождане на дървото по ред.
  • Предварителна поръчка: предварителна поръчка на обръщане на дървото.
  • Пощенска поръчка: обръщане на дървото след поръчка.

Създайте

Първоначално се създава празно дърво без никакви възли. Променливата / идентификаторът, който трябва да сочи към основния възел, се инициализира със   NULL  стойност.

Търсене

Винаги започвате да търсите дървото в кореновия възел и слизате от там. Сравнявате данните във всеки възел с този, който търсите. Ако сравненият възел не съвпада, тогава или пристъпвате към дясното дете или към лявото дете, което зависи от резултата от следното сравнение: Ако възелът, който търсите, е по-нисък от този, с който го сравнявате, продължавате към лявото дете, в противен случай (ако е по-голямо) отивате до дясното дете. Защо? Тъй като BST е структуриран (според дефиницията му), дясното дете винаги е по-голямо от родителя, а лявото дете е винаги по-малко.

Първо търсене на широчина (BFS)

Първото търсене на широчина е алгоритъм, използван за преминаване през BST. Той започва от кореновия възел и пътува странично (отстрани настрани), търсейки желания възел. Този тип търсене може да се опише като O (n), като се има предвид, че всеки възел се посещава веднъж и размерът на дървото директно корелира с дължината на търсенето.

Търсене с дълбочина първо (DFS)

С подход за търсене с дълбочина първо започваме с коренния възел и пътуваме надолу по един клон. Ако желаният възел бъде намерен по този клон, чудесно, но ако не, продължете нагоре и търсете непосетени възли. Този тип търсене също има голяма O нотация на O (n).

Поставете

Той е много подобен на функцията за търсене. Отново започвате от корена на дървото и слизате рекурсивно, търсейки правилното място за вмъкване на новия ни възел, по същия начин, както е обяснено във функцията за търсене. Ако възел със същата стойност вече е в дървото, можете да изберете да вмъкнете дубликата или не. Някои дървета позволяват дубликати, други не. Зависи от конкретното изпълнение.

Изтриване

Има 3 случая, които могат да се случат, когато се опитвате да изтриете възел. Ако има,

  1. Без поддърво (без деца): Това е най-лесното. Можете просто да изтриете възела, без да са необходими допълнителни действия.
  2. Едно поддърво (едно дете): Трябва да се уверите, че след като възелът бъде изтрит, неговото дете след това е свързано с родителя на изтрития възел.
  3. Две поддървета (две деца): Трябва да намерите и замените възела, който искате да изтриете, с неговия наследник inorder (най-левия възел в дясното поддърво).

Сложността във времето за създаване на дърво е   O(1). Сложността във времето за търсене, вмъкване или изтриване на възел зависи от височината на дървото   h, така че най-лошият случай е   O(h)  при изкривени дървета.

Предшественик на възел

Предшествениците могат да бъдат описани като възел, който ще дойде точно преди възела, в който се намирате в момента. За да намерите предшественика на текущия възел, погледнете най-десния / най-големия листен възел в лявото поддърво.

Наследник на възел

Наследниците могат да бъдат описани като възел, който ще дойде веднага след текущия възел. За да намерите наследника на текущия възел, погледнете най-левия / най-малкия листен възел в дясното поддърво.

Специални видове BT

  • Куп
  • Червено-черно дърво
  • B-дърво
  • Splay дърво
  • N-арно дърво
  • Трие (дърво Radix)

Времетраене

Структура на данните: BST

  • Представяне в най-лошия случай:  O(n)
  • Изпълнение в най-добрия случай:  O(1)
  • Средна производителност:  O(log n)
  • Космическа сложност в най-лошия случай:  O(1)

Къде   n  е броят на възлите в BST. Най-лошият случай е O (n), тъй като BST може да бъде небалансиран.

Прилагане на BST

Ето дефиниция за BST възел с някои данни, отнасящ се до неговия ляв и десен дъщерни възли.

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

Операция за търсене

Винаги, когато трябва да се търси елемент, започнете да търсите от основния възел. Тогава, ако данните са по-малки от ключовата стойност, потърсете елемента в лявото поддърво. В противен случай потърсете елемента в дясното поддърво. Следвайте един и същ алгоритъм за всеки възел.

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; } 

Вмъкване на операция

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

While augmenting the tree, we should keep in mind, that we should be able to maintain the augmented information as well as do other operations like insertion, deletion, updating in O(lg n) time.

Since, we know that the value of x.left.size will give us the number of nodes which proceed x in the order traversal of the tree. Thus, x.left.size + 1 is the rank of x within the subtree rooted at x.