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

L'arbre de recherche binaire est également appelé arbre de recherche binaire ou arbre de tri binaire. Un arbre de recherche binaire est organisé comme un arbre binaire et peut être représenté par une structure de données de liste chaînée, dans laquelle chaque nœud est généralement un objet ; , en plus des données clés et satellites, chaque nœud contient également les attributs lchild, rchild et parent.

Arbre de recherche binaire, (aussi : arbre de recherche binaire, arbre de tri binaire) c'est soit un arbre vide, soit un arbre binaire avec les propriétés suivantes : Si son sous-arbre gauche n'est pas vide, alors les valeurs de tous les nœuds du sous-arbre gauche sont inférieures à la valeur de son nœud racine ; Si son sous-arbre droit n'est pas vide, alors les valeurs de tous les nœuds du sous-arbre droit ; ne sont pas vides. Les valeurs de tous les nœuds sont supérieures à la valeur de son nœud racine ; ses sous-arbres gauche et droit sont également respectivement des arbres triés binaires. En tant que structure de données classique, l'arbre de recherche binaire présente les caractéristiques d'opérations d'insertion et de suppression rapides de listes chaînées et l'avantage d'une recherche rapide de tableaux. Par conséquent, il est largement utilisé, par exemple, dans les systèmes de fichiers et les bases de données. Les structures de données effectuent des opérations de tri et de récupération efficaces.

Principe

L'arbre de recherche binaire (BST) est également appelé arbre de recherche binaire ou arbre de tri binaire. Un arbre de recherche binaire est organisé comme un arbre binaire et peut être représenté par une structure de données de liste chaînée, dans laquelle chaque nœud est un objet. Généralement, en plus des données clés et satellites, chaque nœud contient également les attributs lchild, rchild et parent, qui pointent respectivement vers l'enfant gauche, l'enfant droit et les parents (nœuds parents) du nœud. Si un nœud enfant ou un nœud parent n'existe pas, la valeur de l'attribut correspondant est NIL. Le nœud racine est le seul nœud de l'arborescence dont le pointeur parent est NIL, et les pointeurs de nœuds enfants des nœuds feuilles sont également NIL.

Structure

L'arbre de recherche binaire est une structure de données qui peut effectuer efficacement les opérations suivantes.

1. Insérez une valeur

2. Demandez si une certaine valeur est incluse

3.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!