Binaariset hakupuut: BST selitetty esimerkeillä

Mikä on binaarinen hakupuu?

Puu on solmuista koostuva tietorakenne, jolla on seuraavat ominaisuudet:

  1. Jokaisen puun yläosassa on juurisolmu (tunnetaan myös nimellä Vanhempi solmu), joka sisältää jonkin verran arvoa (voi olla mikä tahansa tietotyyppi).
  2. Juurisolmussa on nolla tai useampia alisolmuja.
  3. Jokaisella lapsisolmulla on nolla tai useampia lapsisolmuja ja niin edelleen. Tämä luo alipuun puuhun. Jokaisella solmulla on oma alipuu, joka koostuu lapsistaan ​​ja heidän lapsistaan ​​jne. Tämä tarkoittaa, että jokainen solmu yksin voi olla puu.

Binaarinen hakupuu (BST) lisää nämä kaksi ominaisuutta:

  1. Jokaisessa solmussa on enintään kaksi lasta.
  2. Jokaisen solmun vasemman jälkeläisen solmujen arvot ovat pienemmät kuin nykyisen solmun arvot, mikä puolestaan ​​on pienempi kuin oikean jälkeläisen solmut (jos sellaisia ​​on).

BST perustuu binaarihakualgoritmin ideaan, joka mahdollistaa nopean haun, lisäämisen ja poistamisen solmuista. Tapa, jolla ne asetetaan, tarkoittaa, että kukin vertailu antaa keskimäärin toiminnoille mahdollisuuden ohittaa noin puolet puusta siten, että jokainen haku, lisäys tai poisto vie aikaa suhteessa puuhun tallennettujen kohteiden lukumäärään,   O(log n). Joskus pahin tapaus voi kuitenkin tapahtua, kun puu ei ole tasapainossa ja ajan monimutkaisuus   O(n)  koskee kaikkia näitä kolmea toimintoa. Siksi itsestään tasapainottavat puut (AVL, punamusta jne.) Ovat paljon tehokkaampia kuin perus BST.

Pahimmassa tilanteessa oleva esimerkki:  Tämä voi tapahtua, kun lisäät jatkuvasti solmuja, jotka ovat   aina  suurempia kuin solmu aiemmin (sen vanhempi), sama voi tapahtua, kun lisäät solmuja, joiden arvot ovat pienempiä kuin heidän vanhempansa.

Perustoiminnot BST: llä

  • Luo: luo tyhjän puun.
  • Lisää: lisää solmu puuhun.
  • Haku: etsii solmua puusta.
  • Poista: poistaa solmun puusta.
  • Inorder: puun läpikäynti järjestyksessä.
  • Ennakkotilaus: Puun etukäteen tilaaminen.
  • Postorder: puun jälkikäynti.

Luoda

Aluksi luodaan tyhjä puu ilman solmuja. Muuttuja / tunniste, jonka on osoitettava juurisolmuun, alustetaan   NULL  arvolla.

Hae

Aloitat aina puun etsimisen juurisolmusta ja menet sieltä alas. Verrataan kunkin solmun tietoja etsimääsi. Jos verrattu solmu ei täsmää, siirryt joko oikeaan tai vasempaan lapseen, mikä riippuu seuraavan vertailun tuloksesta: Jos etsimäsi solmu on pienempi kuin vertailtu solmu, siirryt vasemmalle lapselle, muuten (jos se on suurempi) menet oikealle lapselle. Miksi? Koska BST on jäsennelty (määritelmänsä mukaan), oikea lapsi on aina suurempi kuin vanhempi ja vasen lapsi on aina pienempi.

Leveys ensimmäinen haku (BFS)

Leveyshaku on algoritmi, jota käytetään BST: n kulkemiseen. Se alkaa juurisolmusta ja kulkee sivusuunnassa (puolelta toiselle) etsimällä haluttua solmua. Tämän tyyppistä hakua voidaan kuvata nimellä O (n), koska jokaisessa solmussa käydään kerran ja puun koko korreloi suoraan haun pituuden kanssa.

Syvyyden ensimmäinen haku (DFS)

Syvyys ensin -hakutoiminnolla aloitamme juurisolmusta ja siirrymme alas yhdestä haarasta. Jos haluttu solmu löytyy haarasta, hieno, mutta jos ei, jatka ylöspäin ja etsi etsimättömiä solmuja. Tämän tyyppisellä haulla on myös suuri O-merkintä O (n).

Lisää

Se on hyvin samanlainen kuin hakutoiminto. Aloitat jälleen puun juuresta ja menet alas rekursiivisesti etsimällä oikeaa paikkaa uuden solmun lisäämiseen samalla tavalla kuin hakutoiminnossa selitetään. Jos sama arvoinen solmu on jo puussa, voit joko lisätä kopion vai ei. Jotkut puut sallivat kaksoiskappaleet, toiset eivät. Se riippuu tietystä toteutuksesta.

Poistaminen

Kolme tapausta voi tapahtua, kun yrität poistaa solmua. Jos on,

  1. Ei alipuuta (ei lapsia): Tämä on helpoin. Voit yksinkertaisesti poistaa solmun ilman lisätoimenpiteitä.
  2. Yksi alipuu (yksi lapsi): Sinun on varmistettava, että solmun poistamisen jälkeen sen lapsi yhdistetään poistetun solmun vanhempaan.
  3. Kaksi alipuuta (kaksi lasta): Sinun on löydettävä poistettava solmu ja korvattava sen peräkkäin (vasemmanpuoleisin solmu oikeanpuoleisessa alipuussa).

Ajan monimutkaisuus puun luomisessa on   O(1). Solmun etsinnän, lisäämisen tai poistamisen ajan monimutkaisuus riippuu puun korkeudesta   h, joten pahin tapa on   O(h)  vinojen puiden tapauksessa.

Solmun edeltäjä

Edeltäjiä voidaan kuvata solmuksi, joka tulee juuri ennen solmua, jolla olet tällä hetkellä. Löydät nykyisen solmun edeltäjän katsomalla vasemman alipuun oikeanpuoleisin / suurin lehtisolmu.

Solmun seuraaja

Seuraajaa voidaan kuvata solmuksi, joka tulisi heti nykyisen solmun jälkeen. Löydät nykyisen solmun seuraajan katsomalla oikean alipuun vasemmanpuoleisin / pienin lehtisolmu.

Erityiset BT-tyypit

  • Pino
  • Punainen-musta puu
  • B-puu
  • Splay puu
  • N-ary puu
  • Trie (Radix-puu)

Ajonaika

Tietorakenne: BST

  • Huonoin tapa:  O(n)
  • Paras suorituskyky:  O(1)
  • Keskimääräinen suorituskyky:  O(log n)
  • Pahimmassa tapauksessa tilan monimutkaisuus:  O(1)

Missä   n  on BST: n solmujen määrä. Pahin tapaus on O (n), koska BST voi olla epätasapainossa.

BST: n toteutus

Tässä on määritelmä BST-solmulle, jolla on joitain tietoja, viitaten sen vasempaan ja oikeaan lapsisolmuun.

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

Hakutoiminto

Aina kun elementtiä haetaan, aloita haku juurisolmusta. Sitten, jos tiedot ovat pienempiä kuin avainarvo, etsi elementti vasemmasta alipuusta. Muussa tapauksessa etsi elementti oikeasta alipuusta. Seuraa samaa algoritmia jokaiselle solmulle.

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

Lisää toiminta

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

Puun kasvattamisen aikana meidän on pidettävä mielessä, että meidän on pystyttävä ylläpitämään lisätyt tiedot sekä tekemään muita toimintoja, kuten lisääminen, poistaminen ja päivittäminen O(lg n)ajoissa.

Koska tiedämme, että x.left.size-arvo antaa meille solmujen määrän, jotka jatkavat x: tä puun järjestyksessä. Siten x.left.size + 1on x: n sijoitus alipuussa, joka juurtuu kohtaan x.