Arbres de recherche binaires: BST expliqué avec des exemples

Qu'est-ce qu'un arbre de recherche binaire?

Un arbre est une structure de données composée de nœuds qui présente les caractéristiques suivantes:

  1. Chaque arbre a un nœud racine en haut (également connu sous le nom de nœud parent) contenant une valeur (peut être n'importe quel type de données).
  2. Le nœud racine a zéro ou plusieurs nœuds enfants.
  3. Chaque nœud enfant a zéro ou plusieurs nœuds enfants, et ainsi de suite. Cela crée un sous-arbre dans l'arborescence. Chaque nœud a son propre sous-arbre composé de ses enfants et de leurs enfants, etc. Cela signifie que chaque nœud seul peut être un arbre.

Un arbre de recherche binaire (BST) ajoute ces deux caractéristiques:

  1. Chaque nœud a un maximum de deux enfants.
  2. Pour chaque nœud, les valeurs de ses nœuds descendants gauches sont inférieures à celles du nœud actuel, qui à son tour est inférieure aux nœuds descendants droits (le cas échéant).

Le BST est construit sur l'idée de l'algorithme de recherche binaire, qui permet une recherche, une insertion et une suppression rapides des nœuds. La façon dont ils sont mis en place signifie qu'en moyenne, chaque comparaison permet aux opérations de sauter environ la moitié de l'arbre, de sorte que chaque recherche, insertion ou suppression prend un temps proportionnel au logarithme du nombre d'éléments stockés dans l'arbre,   O(log n). Cependant, le pire des cas peut parfois arriver, lorsque l'arbre n'est pas équilibré et que la complexité temporelle est   O(n)  pour ces trois fonctions. C'est pourquoi les arbres auto-équilibrés (AVL, rouge-noir, etc.) sont beaucoup plus efficaces que le BST de base.

Exemple de scénario dans le pire des cas:  cela peut se produire lorsque vous continuez à ajouter des nœuds   toujours  plus grands que le nœud précédent (son parent), la même chose peut se produire lorsque vous ajoutez toujours des nœuds avec des valeurs inférieures à leurs parents.

Opérations de base sur un BST

  • Créer: crée un arbre vide.
  • Insérer: insérez un nœud dans l'arborescence.
  • Rechercher: recherche un nœud dans l'arborescence.
  • Supprimer: supprime un nœud de l'arborescence.
  • Inorder: parcours dans l'ordre de l'arbre.
  • Précommande: parcours de pré-commande de l'arbre.
  • Postorder: parcours post-ordre de l'arbre.

Créer

Initialement, une arborescence vide sans aucun nœud est créée. La variable / identifiant qui doit pointer vers le nœud racine est initialisée avec une   NULL  valeur.

Chercher

Vous commencez toujours à rechercher l'arborescence au nœud racine et à partir de là. Vous comparez les données de chaque nœud avec celui que vous recherchez. Si le nœud comparé ne correspond pas, vous passez soit à l'enfant droit, soit à l'enfant gauche, ce qui dépend du résultat de la comparaison suivante: Si le nœud que vous recherchez est inférieur à celui avec lequel vous le compariez, vous passez à l'enfant gauche, sinon (s'il est plus grand) vous allez à l'enfant droit. Pourquoi? Parce que le BST est structuré (selon sa définition), l'enfant droit est toujours plus grand que le parent et l'enfant gauche est toujours inférieur.

Recherche en largeur d'abord (BFS)

La première recherche en largeur est un algorithme utilisé pour parcourir un BST. Il commence au nœud racine et se déplace de manière latérale (côte à côte), à ​​la recherche du nœud souhaité. Ce type de recherche peut être décrit comme O (n) étant donné que chaque nœud est visité une fois et que la taille de l'arbre est directement corrélée à la longueur de la recherche.

Recherche en profondeur d'abord (DFS)

Avec une approche de recherche en profondeur d'abord, nous commençons par le nœud racine et descendons une seule branche. Si le nœud souhaité se trouve le long de cette branche, très bien, mais sinon, continuez vers le haut et recherchez les nœuds non visités. Ce type de recherche a également une grande notation O de O (n).

Insérer

C'est très similaire à la fonction de recherche. Vous recommencez à la racine de l'arbre et descendez récursivement, en recherchant le bon endroit pour insérer notre nouveau nœud, de la même manière que celle expliquée dans la fonction de recherche. Si un nœud avec la même valeur est déjà dans l'arborescence, vous pouvez choisir d'insérer le doublon ou non. Certains arbres autorisent les doublons, d'autres non. Cela dépend de la mise en œuvre certaine.

Effacement

Il y a 3 cas qui peuvent se produire lorsque vous essayez de supprimer un nœud. Si c'est le cas,

  1. Pas de sous-arbre (pas d'enfants): celui-ci est le plus simple. Vous pouvez simplement supprimer le nœud, sans aucune action supplémentaire requise.
  2. Un sous-arbre (un enfant): vous devez vous assurer qu'après la suppression du nœud, son enfant est alors connecté au parent du nœud supprimé.
  3. Deux sous-arbres (deux enfants): Vous devez rechercher et remplacer le nœud que vous souhaitez supprimer par son successeur inorder (le nœud le plus à gauche dans le sous-arbre de droite).

La complexité du temps pour créer un arbre est   O(1). La complexité temporelle de la recherche, de l'insertion ou de la suppression d'un nœud dépend de la hauteur de l'arbre   h, le pire des cas est donc   O(h)  celui des arbres asymétriques.

Prédécesseur d'un nœud

Les prédécesseurs peuvent être décrits comme le nœud qui viendrait juste avant le nœud dans lequel vous vous trouvez actuellement. Pour trouver le prédécesseur du nœud actuel, regardez le nœud feuille le plus à droite / le plus grand dans le sous-arbre gauche.

Successeur d'un nœud

Les successeurs peuvent être décrits comme le nœud qui viendrait juste après le nœud actuel. Pour trouver le successeur du nœud actuel, regardez le nœud feuille le plus à gauche / le plus petit dans le sous-arbre de droite.

Types spéciaux de BT

  • Tas
  • Arbre rouge-noir
  • Arbre B
  • Arbre Splay
  • Arbre N-aire
  • Trie (arbre Radix)

Durée

Structure des données: BST

  • Pires performances des cas:  O(n)
  • Meilleures performances:  O(1)
  • Performance moyenne:  O(log n)
  • Complexité de l'espace dans le pire des cas:  O(1)

Où   n  est le nombre de nœuds dans le BST. Le pire des cas est O (n) car BST peut être déséquilibré.

Mise en œuvre de BST

Voici une définition d'un nœud BST contenant des données, faisant référence à ses nœuds enfants gauche et droit.

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

Opération de recherche

Chaque fois qu'un élément doit être recherché, lancez la recherche à partir du nœud racine. Ensuite, si les données sont inférieures à la valeur de clé, recherchez l'élément dans le sous-arbre de gauche. Sinon, recherchez l'élément dans le sous-arbre de droite. Suivez le même algorithme pour chaque nœud.

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

Insérer une opération

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.