Binaarotsingupuud: BST selgitatud näidetega

Mis on binaarne otsingupuu?

Puu on sõlmedest koosnev andmestruktuur, millel on järgmised omadused:

  1. Igal puul on ülaosas juursõlm (tuntud ka kui vanemsõlm), mis sisaldab mõnda väärtust (võib olla mis tahes andmetüüp).
  2. Juuresõlmel on null või rohkem alamsõlme.
  3. Igal lapsesõlmel on null või rohkem alamsõlme jne. See loob puusse alampuu. Igal sõlmel on oma alampuu, mis koosneb tema lastest ja nende lastest jne. See tähendab, et iga omaette sõlm võib olla puu.

Binaarotsingupuu (BST) lisab need kaks omadust:

  1. Igas sõlmes on maksimaalselt kuni kaks last.
  2. Iga sõlme puhul on tema vasakpoolsete järeltulevate sõlmede väärtused väiksemad kui praeguse sõlme väärtused, mis omakorda on väiksem kui parempoolsete järeltulevate sõlmede (kui neid on).

BST on üles ehitatud binaarse otsingu algoritmi ideele, mis võimaldab sõlme kiiret otsimist, sisestamist ja eemaldamist. Nende seadistamine tähendab, et keskmiselt võimaldab iga võrdlus toimingutel umbes pool puust vahele jätta, nii et iga otsimine, lisamine või kustutamine võtab aega, mis on proportsionaalne puusse salvestatud üksuste arvu logaritmiga.   O(log n). Mõnikord võib juhtuda halvim juhtum, kui puu pole tasakaalus ja aja keerukus on   O(n)  kõigi nende kolme funktsiooni jaoks. Seetõttu on isetasakaalustuvad puud (AVL, punane-must jne) palju tõhusamad kui põhiline BST.

Halvima stsenaariumi näide:  see võib juhtuda, kui lisate pidevalt sõlmi, mis on   alati  suuremad kui varasem sõlm (selle vanem), sama võib juhtuda ka siis, kui lisate alati nende vanematest madalamate väärtustega sõlmed.

Põhitoimingud BST-is

  • Loo: loob tühja puu.
  • Insert: sisestage puusse sõlm.
  • Otsing: otsib puust sõlme.
  • Kustuta: kustutab puust sõlme.
  • Inorder: puu korrapärane läbimine.
  • Ettetellimine: puu ettetellimine.
  • Postorder: puu tellimusjärgne läbimine.

Loo

Esialgu luuakse tühi puu ilma sõlmedeta. Muutuja / identifikaator, mis peab osutama juursõlmele, lähtestatakse   NULL  väärtusega.

Otsing

Alustate puu otsimist alati juuresõlmest ja lähete sealt alla. Võrdlete iga sõlme andmeid otsituga. Kui võrreldav sõlm ei ühti, jätkate kas parema või vasaku lapse poole, mis sõltub järgmise võrdluse tulemustest: Kui otsitav sõlm on madalam kui sellega, millega te seda võrdlesite, jätkate vasakule lapsele, vastasel juhul (kui see on suurem) lähete õige lapse juurde. Miks? Kuna BST on struktureeritud (vastavalt selle määratlusele), on õige laps alati vanemast suurem ja vasak laps alati väiksem.

Laiuse esimene otsing (BFS)

Laiuse esimene otsing on algoritm, mida kasutatakse BST läbimiseks. See algab juursõlmest ja liigub külgsuunas (küljelt küljele), otsides soovitud sõlme. Seda tüüpi otsingut võib kirjeldada kui O (n), kuna iga sõlme külastatakse üks kord ja puu suurus on otseses vastavuses otsingu pikkusega.

Esimene sügavusotsing (DFS)

Sügavuse-esimese otsingu lähenemisega alustame juursõlmest ja liigume ühe haruga alla. Kui soovitud sõlm leitakse selle haru ääres, on suurepärane, kuid kui ei, jätkake ülespoole ja otsige külastamata sõlme. Seda tüüpi otsingutel on ka suur O tähis O (n).

Sisesta

See sarnaneb väga otsingufunktsiooniga. Alustate taas puu juurest ja lähete rekursiivselt alla, otsides meie uue sõlme sisestamiseks õiget kohta, samamoodi nagu otsingufunktsioonis selgitatud. Kui sama väärtusega sõlm on juba puus, võite valida kas duplikaadi sisestamise või mitte. Mõni puu lubab duplikaate, mõni mitte. See sõltub kindlast rakendamisest.

Kustutamine

Sõlme kustutamisel võib juhtuda 3 juhtumit. Kui on,

  1. Alampuid pole (lapsi pole): see on kõige lihtsam. Saate sõlme lihtsalt kustutada, ilma et oleks vaja täiendavaid toiminguid.
  2. Üks alampuu (üks laps): peate veenduma, et pärast sõlme kustutamist ühendatakse selle laps kustutatud sõlme vanemaga.
  3. Kaks alampuud (kaks last): peate leidma ja asendama kustutatava sõlme selle järeltulijaga (parempoolse alampuu kõige vasakpoolsem sõlm).

Puu loomise ajaline keerukus on   O(1). Sõlme otsimise, sisestamise või kustutamise ajaline keerukus sõltub puu kõrgusest   h, seega on halvim juhtum   O(h)  viltu puude korral.

Sõlme eelkäija

Eelkäijaid võib kirjeldada kui sõlme, mis tuleks otse enne seda sõlme, kus praegu viibite. Praeguse sõlme eelkäija leidmiseks vaadake vasakpoolse alampuu kõige paremat / suuremat lehesõlme.

Sõlme järglane

Järglasi võib kirjeldada kui sõlme, mis tuleks kohe pärast praegust sõlme. Praeguse sõlme järglase leidmiseks vaadake parempoolse alampuu kõige vasakpoolsemat / väiksemat lehesõlme.

BT eriliigid

  • Hunnik
  • Punamust puu
  • B-puu
  • Mängupuu
  • N-ary puu
  • Trie (Radixi puu)

Kestus

Andmete struktuur: BST

  • Halvimal juhul:  O(n)
  • Parimal juhul:  O(1)
  • Keskmine jõudlus:  O(log n)
  • Halvimal juhul on ruumi keerukus:  O(1)

Kus   n  on BST-i sõlmede arv. Halvim juhtum on O (n), kuna BST võib olla tasakaalust väljas.

BST rakendamine

Siin on BST-sõlme määratlus, millel on mõned andmed, viidates selle vasakule ja paremale alamsõlmele.

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

Otsinguoperatsioon

Alati, kui soovitakse elementi otsida, alustage otsimist juursõlmest. Kui andmed on võtmeväärtusest väiksemad, otsige vasakpoolsest alampuust elementi. Muul juhul otsige elementi paremast alampuust. Järgige iga sõlme sama algoritmi.

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

Sisesta toiming

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

Puu suurendamise ajal peaksime meeles pidama, et peaksime olema võimelised nii täiendatud teavet säilitama kui ka muid toiminguid nagu O(lg n)õigeaegne sisestamine, kustutamine ja värskendamine .

Kuna me teame, et x.left.size väärtus annab meile arvu sõlme, mis jätkavad x-i puu järjestuse läbimisel. Seega x.left.size + 1on x auaste x-is juurdunud alampuus.