Binære søgetræer: BST forklaret med eksempler

Hvad er et binært søgetræ?

Et træ er en datastruktur sammensat af noder, der har følgende egenskaber:

  1. Hvert træ har en rodnode øverst (også kendt som forældrenode), der indeholder en værdi (kan være en hvilken som helst datatype).
  2. Rodknudepunktet har nul eller flere underknudepunkter.
  3. Hver barneknude har nul eller flere underknudepunkter osv. Dette skaber et undertræ i træet. Hver knude har sit eget undertræ, der består af sine børn og deres børn osv. Det betyder, at hver knude alene kan være et træ.

Et binært søgetræ (BST) tilføjer disse to egenskaber:

  1. Hver knude har maksimalt op til to børn.
  2. For hvert knudepunkt er værdierne for dets venstre nedadgående knudepunkter mindre end værdien for den aktuelle knude, hvilket igen er mindre end de højre nedadgående knudepunkter (hvis nogen).

BST er bygget på ideen om den binære søgealgoritme, som giver mulighed for hurtig opslag, indsættelse og fjernelse af noder. Den måde, de er opstillet på, betyder, at hver sammenligning i gennemsnit giver operationerne mulighed for at springe over halvdelen af ​​træet, så hver opslag, indsættelse eller sletning tager tid, der er proportional med logaritmen for antallet af genstande, der er gemt i træet,   O(log n). Imidlertid kan nogle gange det værste tilfælde ske, når træet ikke er afbalanceret, og tidskompleksiteten gælder   O(n)  for alle disse tre funktioner. Derfor er selvbalancerende træer (AVL, rød-sort osv.) Meget mere effektive end den grundlæggende BST.

Eksempel på værste tilfælde:  Dette kan ske, når du fortsætter med at tilføje noder, der   altid er  større end noden før (dens overordnede), det samme kan ske, når du altid tilføjer noder med værdier lavere end deres forældre.

Grundlæggende operationer på en BST

  • Opret: opretter et tomt træ.
  • Indsæt: indsæt en node i træet.
  • Søgning: Søger efter en node i træet.
  • Slet: sletter en node fra træet.
  • Inorder: i rækkefølge gennemkørsel af træet.
  • Forudbestilling: Forudbestil gennemkørsel af træet.
  • Postorder: post-order gennemkørsel af træet.

skab

Oprindeligt oprettes et tomt træ uden noder. Variablen / identifikatoren, der skal pege på rodnoden, initialiseres med en   NULL  værdi.

Søg

Du begynder altid at søge i træet ved rodnoden og går ned derfra. Du sammenligner dataene i hver node med den, du leder efter. Hvis det sammenlignede knudepunkt ikke stemmer overens, fortsætter du enten til det rigtige barn eller det venstre barn, hvilket afhænger af resultatet af følgende sammenligning: Hvis den node, du søger efter, er lavere end den, du sammenlignede den med, du går videre til det venstre barn, ellers går du til det rigtige barn (hvis det er større). Hvorfor? Fordi BST er struktureret (ifølge definitionen), er det rigtige barn altid større end forældren, og det venstre barn er altid mindre.

Bredde-første søgning (BFS)

Første søgning i bredde er en algoritme, der bruges til at krydse en BST. Den begynder ved rodnoden og bevæger sig på en lateral måde (side til side) og søger efter den ønskede node. Denne type søgning kan beskrives som O (n), forudsat at hver node besøges en gang, og størrelsen på træet korrelerer direkte med søgningens længde.

Dybde-første søgning (DFS)

Med en dybde-første søgemetode starter vi med rodnoden og bevæger os ned ad en enkelt gren. Hvis den ønskede knudepunkt findes langs den gren, fantastisk, men hvis ikke, skal du fortsætte opad og søge i ubesøgte noder. Denne type søgning har også en stor O-notation af O (n).

Indsæt

Det ligner meget søgefunktionen. Du starter igen ved roden af ​​træet og går ned rekursivt og søger efter det rigtige sted at indsætte vores nye knude på samme måde som forklaret i søgefunktionen. Hvis en knude med den samme værdi allerede findes i træet, kan du vælge enten at indsætte duplikatet eller ikke. Nogle træer tillader duplikater, andre gør det ikke. Det afhænger af den bestemte implementering.

Sletning

Der er 3 tilfælde, der kan ske, når du prøver at slette en node. Hvis det har,

  1. Intet undertræ (ingen børn): Denne er den nemmeste. Du kan bare slette noden uden yderligere handlinger nødvendige.
  2. Et undertræ (et barn): Du skal sørge for, at efter at noden er slettet, er dens barn derefter forbundet til den slettede nodes forælder.
  3. To undertræer (to børn): Du skal finde og erstatte den node, du vil slette, med dens ordrefølger (den længste venstre node i højre undertræ).

Tidenes kompleksitet for at skabe et træ er   O(1). Tidskompleksiteten for søgning, indsættelse eller sletning af en node afhænger af træets højde   h, så det værste tilfælde er   O(h)  i tilfælde af skæve træer.

Forløber for en knude

Forgjengere kan beskrives som den node, der ville komme lige før den node, du er i øjeblikket. For at finde forgængeren til den aktuelle knude skal du se på den højre / største bladknude i venstre undertræ.

Efterfølger af en knude

Efterfølgere kan beskrives som den node, der ville komme lige efter den aktuelle node. For at finde efterfølgeren til den aktuelle knude, se på den venstre / mindste bladknude i højre undertræ.

Specielle typer BT

  • Bunke
  • Rød-sort træ
  • B-træ
  • Splay træ
  • N-ary træ
  • Trie (Radix træ)

Kørselstid

Datastruktur: BST

  • Værst tænkelig ydeevne:  O(n)
  • Bedste case ydeevne:  O(1)
  • Gennemsnitlig ydeevne:  O(log n)
  • Værst-plads-kompleksitet:  O(1)

Hvor   n  er antallet af noder i BST. Det værste tilfælde er O (n), da BST kan være ubalanceret.

Implementering af BST

Her er en definition af en BST-node, der har nogle data, der henviser til dens venstre og højre underordnede noder.

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

Søgning

Når et element skal søges, skal du begynde at søge fra rodnoden. Så hvis dataene er mindre end nøgleværdien, skal du søge efter elementet i venstre undertræ. Ellers skal du søge efter elementet i det rigtige undertræ. Følg den samme algoritme for hver 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; } 

Indsæt 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

Mens vi udvider træet, skal vi huske på, at vi skal være i stand til at vedligeholde de udvidede oplysninger samt udføre andre operationer som indsættelse, sletning, opdatering i O(lg n)tide.

Da vi ved, at værdien af ​​x.left.size giver os antallet af noder, der fortsætter x i rækkefølge af træet. Således x.left.size + 1er rangeringen af ​​x inden for undertræet rodfæstet ved x.