Un Arbre de recherche binaire (BST) est un arbre dans lequel tous les nœuds suivent les propriétés mentionnées ci-dessous −
-
la valeur de la clé du sous-arbre gauche est inférieure à la valeur de la clé de son nœud parent (racine).
-
la valeur de La clé de la droite du sous-arbre est supérieure ou égale à la valeur de son parent (racine) du nœud de clé.,
ainsi, BST divise tous ses sous-arbres en deux segments; le sous-arbre gauche et le sous-arbre droit et peut être défini comme −
left_subtree (keys) < node (key) ≤ right_subtree (keys)
représentation
BST est une collection de nœuds disposés de manière à conserver les propriétés BST. Chaque nœud possède une clé et une valeur associée. Lors de la recherche, la clé souhaitée est comparée aux clés dans BST et si elle est trouvée, la valeur associée est récupérée.,
Voici une représentation picturale DE BST −
Nous observons que la clé du nœud racine (27) a toutes les clés de valeur inférieure sur le sous-arbre de gauche et les clés de valeur supérieure sur le sous-arbre de droite.
opérations de base
Voici les opérations de base d’un arbre −
-
Search − Recherche un élément dans un arbre.
-
Insert Insère un élément dans un arbre.
-
Pré-commander la Traversée − Parcourt un arbre dans un pré-commander manière.
-
Dans l’ordre de la Traversée − Parcourt un arbre dans un ordre de manière.,
-
traversée Post-ordre − traverse un arbre de manière post-ordre.
Node
définir un nœud ayant des données, des références à 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é, commencez la recherche à partir du nœud racine. Ensuite, si les données sont inférieures à la valeur 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.,
l’Algorithme
Insertion
Chaque fois qu’un élément est inséré, d’abord localiser son emplacement approprié. Commencez la recherche à partir du nœud racine, puis si les données sont inférieures à la valeur de la clé, recherchez l’Emplacement vide dans le sous-arbre de gauche et insérez les données. Sinon, recherchez l’Emplacement vide dans le sous-arbre de droite et insérez les données.