Structure des données de l'arborescence de recherche binaire expliquée avec des exemples

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) ayant une certaine valeur.
  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 qui sont toujours plus grands que le nœud précédent (c'est le 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.

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 NULLvaleur.

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.

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.

Supprimer

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 trouver et remplacer le nœud que vous souhaitez supprimer par son successeur (le nœud le plus en bas dans le sous-arbre de droite).

La complexité du temps pour créer un arbre est O(1). La complexité du temps pour rechercher, insérer ou supprimer un nœud dépend de la hauteur de l'arbre h, donc le pire des cas est O(h).

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 dans lequel vous vous trouvez actuellement. 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: Array

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

nest le nombre de nœuds dans le BST.

Mise en œuvre de BST

Voici une définition pour un nœud BST ayant 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; } } } } } 

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

Relevant videos on freeCodeCamp YouTube channel

  • Binary Search Tree
  • 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