A quoi sert l'arbre de recherche binaire ?

Les arbres de recherche binaires sont principalement utilisés pour la recherche et le tri dynamique. La complexité temporelle de "l'insertion/requête/suppression" des arbres binaires est "O(log(n))", mais elle n'est généralement pas utilisée dans. utilisation réelle. C'est si rapide parce que le "milieu" utilisé dans l'ordre d'insertion n'est généralement pas si précis.

Le rôle de l'arbre de recherche binaire

Le rôle principal que je connais est la recherche et le tri dynamique, La complexité temporelle de l'insertion/requête/suppression dans un arbre binaire est O(log(n)). Cependant, ce n'est généralement pas si rapide dans l'utilisation réelle, car le milieu utilisé dans l'ordre d'insertion n'est généralement pas aussi précis. Surtout lorsque l'ordre d'insertion des données est ordonné ou fondamentalement ordonné, l'arbre binaire sera sérieusement déséquilibré. Dans ce cas, elle tombera au même niveau qu'une liste chaînée.

Les principales opérations de l'arbre de tri binaire sont :

1 Recherche : rechercher de manière récursive si la clé existe.

2. Insertion : La clé n'existe pas dans l'arborescence d'origine. L'insertion de la clé renvoie vrai, sinon elle renvoie faux.

3. Construction : opération d'insertion de boucle.

4. Supprimer : (1) Nœud feuille : supprimer directement sans affecter l'arborescence d'origine.

(2) Uniquement les nœuds avec des sous-arbres gauche ou droit : une fois le nœud supprimé, déplacez simplement tout son sous-arbre gauche ou son sous-arbre droit vers la position du nœud supprimé, et le fils héritera de l'héritage du père.

(3) Nœuds avec des sous-arbres gauche et droit : recherchez le prédécesseur direct ou les successeurs directs du nœud p qui doit être supprimé, remplacez le nœud p par s, puis supprimez le nœud s.

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!