Binarno drveće pretraživanja: BST objašnjeno s primjerima

Što je binarno stablo pretraživanja?

Stablo je struktura podataka sastavljena od čvorova koja ima sljedeće značajke:

  1. Svako stablo ima korijenski čvor na vrhu (poznat i kao Nadređeni čvor) koji sadrži neku vrijednost (može biti bilo koji tip podataka).
  2. Korijenski čvor ima nula ili više podređenih čvorova.
  3. Svaki podređeni čvor ima nula ili više podređenih čvorova itd. Ovo stvara podstablo na stablu. Svaki čvor ima svoje podstablo koje čine njegova djeca i njihova djeca itd. To znači da svaki čvor sam za sebe može biti stablo.

Binarno stablo pretraživanja (BST) dodaje ove dvije karakteristike:

  1. Svaki čvor ima najviše do dvoje djece.
  2. Za svaki čvor vrijednosti njegovih lijevih čvorova silaznih skupina manje su od vrijednosti trenutnog čvora, a zauzvrat su manje od čvorova desnih potomaka (ako ih ima).

BST je izgrađen na ideji binarnog algoritma pretraživanja, koji omogućuje brzo traženje, umetanje i uklanjanje čvorova. Način na koji su postavljeni znači da u prosjeku svaka usporedba omogućuje operacijama preskakanje oko polovice stabla, tako da svako traženje, umetanje ili brisanje uzima vrijeme proporcionalno logaritmu broja stavki pohranjenih u stablu,   O(log n). Međutim, ponekad se dogodi najgori slučaj kada stablo nije uravnoteženo i složenost vremena je   O(n)  za sve tri ove funkcije. Zbog toga su samobalansirajuća stabla (AVL, crveno-crna, itd.) Puno učinkovitija od osnovnog BST-a.

Primjer najgoreg scenarija:  To se može dogoditi kada nastavite dodavati čvorove koji su   uvijek  veći od čvora prije (njegovog roditelja), isto se može dogoditi kada čvorove uvijek dodate s vrijednostima nižim od njihovih roditelja.

Osnovne operacije na BST-u

  • Stvori: stvara prazno stablo.
  • Umetni: umetnite čvor u stablo.
  • Pretraživanje: traži čvor na drvetu.
  • Delete: briše čvor sa stabla.
  • Unutrašnjost: redoslijed stabala.
  • Predbilježba: unaprijed naručite prelazak stabla.
  • Postorder: prijelaz stabla nakon narudžbe.

Stvoriti

U početku se stvara prazno stablo bez ikakvih čvorova. Varijabla / identifikator koji mora ukazivati ​​na korijenski čvor inicijalizira se   NULL  vrijednošću.

traži

Stablo uvijek započnete pretraživati ​​na korijenskom čvoru i odatle se spuštate dolje. Usporedite podatke u svakom čvoru s onim kojeg tražite. Ako se uspoređeni čvor ne podudara, prelazite na desno ili lijevo dijete, što ovisi o ishodu sljedeće usporedbe: Ako je čvor koji tražite niži od onog s kojim ste ga uspoređivali, nastavljate prema lijevom djetetu, u suprotnom (ako je veće) idete prema desnom djetetu. Zašto? Budući da je BST strukturiran (prema njegovoj definiciji), da je desno dijete uvijek veće od roditelja, a lijevo dijete uvijek manje.

Pretraživanje u širini (BFS)

Pretraživanje širine prvo je algoritam koji se koristi za prelazak BST-a. Počinje na korijenskom čvoru i putuje bočno (bočno uz bok), tražeći željeni čvor. Ova vrsta pretraživanja može se opisati kao O (n) s obzirom na to da se svaki čvor posjeti jednom, a veličina stabla izravno korelira s duljinom pretraživanja.

Dubinsko prvo pretraživanje (DFS)

Pristupom pretraživanja s dubinom započinjemo s korijenskim čvorom i putujemo niz jednu granu. Ako se željeni čvor nađe duž te grane, sjajno, ali ako ne, nastavite prema gore i pretražite ne posjećene čvorove. Ova vrsta pretraživanja također ima veliku O oznaku O (n).

Umetnuti

Vrlo je slična funkciji pretraživanja. Ponovno započinjete od korijena stabla i spuštate se rekurzivno, tražeći pravo mjesto za umetanje našeg novog čvora, na isti način kao što je objašnjeno u funkciji pretraživanja. Ako je čvor s istom vrijednošću već u stablu, možete odabrati umetanje duplikata ili ne. Neka stabla dopuštaju duplikate, neka ne. Ovisi o određenoj provedbi.

Brisanje

Postoje 3 slučaja koja se mogu dogoditi kada pokušavate izbrisati čvor. Ako jest,

  1. Nema podstabla (nema djece): ovo je najlakše. Možete jednostavno izbrisati čvor, bez dodatnih radnji.
  2. Jedno podstablo (jedno dijete): Morate biti sigurni da je nakon brisanja čvora njegovo dijete povezano s roditeljem izbrisanog čvora.
  3. Dva podstabla (dvoje djece): Morate pronaći i zamijeniti čvor koji želite izbrisati sa svojim nasljednikom po redu (krajnji lijevi čvor u desnom podstablu).

Složenost vremena za stvaranje stabla je   O(1). Vremenska složenost pretraživanja, umetanja ili brisanja čvora ovisi o visini stabla   h, pa je najgori slučaj   O(h)  u slučaju iskrivljenih stabala.

Prethodnik čvora

Prethodnici se mogu opisati kao čvor koji bi došao neposredno prije čvora na kojem se trenutno nalazite. Da biste pronašli prethodnika trenutnog čvora, pogledajte krajnji desni / najveći čvor u lijevom podstablu.

Nasljednik čvora

Nasljednici se mogu opisati kao čvor koji će doći odmah nakon trenutnog čvora. Da biste pronašli nasljednika trenutnog čvora, pogledajte krajnji lijevi / najmanji čvor u desnom podstablu.

Posebne vrste BT

  • Hrpa
  • Crveno-crno stablo
  • B-drvo
  • Splavo drvo
  • N-arno drvo
  • Trie (stablo Radix)

Vrijeme izvođenja

Struktura podataka: BST

  • U najgorem slučaju:  O(n)
  • Najbolje izvedbe:  O(1)
  • Prosječna izvedba:  O(log n)
  • Složenost prostora u najgorem slučaju:  O(1)

Gdje   n  je broj čvorova u BST-u. Najgori je slučaj O (n) jer BST može biti neuravnotežen.

Provedba BST-a

Evo definicije za BST čvor koji ima neke podatke, pozivajući se na njegov lijevi i desni podređeni čvor.

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

Operacija pretraživanja

Kad god treba pretražiti element, započnite pretraživanje s korijenskog čvora. Zatim, ako su podaci manji od vrijednosti ključa, potražite element u lijevom podstablu. U suprotnom, potražite element u pravom podstablu. Slijedite isti algoritam za svaki čvor.

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

Umetni rad

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.