Arbre de recherche binaire - une base de données structurée contenant des nœuds, deux liens vers d'autres nœuds, à droite et à gauche. Les nœuds sont un objet de la classe qui contient des données, et NULL est le signe qui marque la fin de l'arbre.
On l'appelle souvent BST, qui a une propriété spéciale: les nœuds plus grands que la racine sont situés à sa droite, et les plus petits à sa gauche.
Théorie générale et terminologie
Dans un arbre de recherche binaire, chaque nœud, à l'exception de la racine, est connecté par une arête dirigée d'un nœud à l'autre, appelée le parent. Chacun d'eux peut être connecté à un nombre arbitraire de nœuds, appelés enfants. Les nœuds sans "enfants" sont appelés feuilles (nœuds externes). Les éléments qui ne sont pas des feuilles sont appelés internes. Les nœuds avec le même parent sont des frères et sœurs. Le nœud le plus haut est appelé la racine. Dans BST, affectez un élément à chaque nœud et assurez-vous qu'ils ont une propriété spéciale définie pour eux.
Terminologie arborescente:
- La profondeur d'un nœud est le nombre d'arêtes définies de la racine à celui-ci.
- La hauteur d'un nœud est le nombre d'arêtes définies depuis celui-ci jusqu'à la feuille la plus profonde.
- La hauteur de l'arbre est déterminée par la hauteur de la racine.
- L'arbre de recherche binaire est une conception spéciale, il fournit le meilleur rapport entre la hauteur et le nombre de nœuds.
- Hauteur h avec N nœuds au plus O (log N).
Vous pouvez facilement le prouver en comptant les nœuds à chaque niveau, en commençant par la racine, en supposant qu'elle en contient le plus grand nombre: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Résoudre ceci pour h donne h=O (log n).
Avantages du bois:
- Reflètent les relations structurelles des données.
- Utilisé pour représenter les hiérarchies.
- Assurez-vous d'une installation et d'une recherche efficaces.
- Les arbres sont des données très flexibles, vous permettant de déplacer des sous-arbres avec un minimum d'effort.
Méthode de recherche
En général, pour déterminer si une valeur est dans le BST, démarrez un arbre de recherche binaire à sa racine et déterminez s'il répond aux exigences:
- être à la racine;
- être dans le sous-arbre gauche de la racine;
- dans le sous-arbre droit de la racine.
Si aucun registre de base n'est satisfait, une recherche récursive est effectuée dans le sous-arbre correspondant. Il existe en fait deux options de base:
- L'arbre est vide - renvoie faux.
- La valeur est dans le nœud racine - renvoie vrai.
Il convient de noter qu'un arbre de recherche binaire avec un schéma développé commence toujours à chercher le long du chemin de la racine à la feuille. Dans le pire des cas, il va jusqu'à la feuille. Par conséquent, le pire moment est proportionnel à la longueur du chemin le plus long de la racine à la feuille, qui est la hauteur de l'arbre. En général, c'est à ce moment qu'il faut savoir combien de temps il faut pour chercher en fonction du nombre de valeurs stockées dans l'arborescence.
En d'autres termes, il existe une relation entre le nombre de nœuds dans un BST et la hauteur d'un arbre, en fonction de sa "forme". Dans le pire des cas, les nœuds n'ont qu'un seul enfant et un arbre de recherche binaire équilibré est essentiellement une liste chaînée. Par exemple:
50
/
10
15
30
/
20
Cet arbre a 5 nœuds et hauteur=5. Trouver des valeurs dans la plage 16-19 et 21-29 nécessitera le chemin suivant de la racine à la feuille (le nœud contenant la valeur 20), c'est-à-dire, cela prendra un temps proportionnel au nombre de nœuds. Au mieux, ils ont tous 2 enfants, et les feuilles sont situées à la même profondeur.
Cet arbre de recherche binaire a 7 nœuds et hauteur=3. En général, un arbre comme celui-ci (arbre complet) aura une hauteur d'environ log 2 (N), où N est le nombre de nœuds dans l'arbre. La valeur de log 2 (N) est le nombre de fois (2) que N peut être divisé avant que zéro ne soit atteint.
Résumé: le pire temps nécessaire pour effectuer une recherche dans BST est O (hauteur de l'arbre). L'arbre "linéaire" dans le pire des cas est O(N), où N est le nombre de nœuds dans l'arbre. Au mieux, un arbre "complet" est O(log N).
Insert binaire BST
Je me demande où devrait êtrele nouveau nœud est situé dans le BST, vous devez comprendre la logique, il doit être placé là où l'utilisateur le trouve. De plus, vous devez vous rappeler les règles:
- Les doublons ne sont pas autorisés, tenter d'insérer une valeur en double lèvera une exception.
- La méthode d'insertion publique utilise une méthode "helper" récursive d'assistance pour réellement insérer.
- Un nœud contenant une nouvelle valeur est toujours inséré en tant que feuille dans BST.
- La méthode d'insertion publique renvoie void, mais la méthode d'assistance renvoie un BSTnode. Il le fait pour gérer le cas où le nœud qui lui est transmis est nul.
En général, la méthode d'assistance indique que si l'arbre de recherche binaire d'origine est vide, le résultat est un arbre à un nœud. Sinon, le résultat sera un pointeur vers le même nœud qui a été passé en argument.
Suppression dans l'algorithme binaire
Comme vous vous en doutez, la suppression d'un élément implique la recherche d'un nœud contenant la valeur à supprimer. Il y a plusieurs choses dans ce code:
- BST utilise une méthode de suppression surchargée. Si l'élément que vous recherchez n'est pas dans l'arbre, la méthode d'assistance sera éventuellement appelée avec n==null. Ceci n'est pas considéré comme une erreur, l'arbre ne change tout simplement pas dans ce cas. La méthode d'assistance de suppression renvoie une valeur - un pointeur vers l'arborescence mise à jour.
- Lorsqu'une feuille est supprimée, la suppression de l'arbre de recherche binaire définit le pointeur enfant correspondant de son parent sur null, ou la racine sur null si celle qui est supprimée estle nœud est une racine et n'a pas d'enfant.
- Notez que l'appel de suppression doit être l'un des suivants: root=delete (racine, clé), n.setLeft (delete (n.getLeft (), clé)), n.setRight (delete(n. getRight(), clé)). Ainsi, dans les trois cas, il est correct que la méthode de suppression renvoie simplement null.
- Lorsque la recherche du nœud contenant la valeur à supprimer aboutit, trois options s'offrent à vous: le nœud à supprimer est une feuille (n'a pas d'enfant), le nœud à supprimer a un enfant, il en a deux enfants.
- Lorsque le nœud supprimé a un enfant, vous pouvez simplement le remplacer par un enfant, renvoyant un pointeur vers l'enfant.
- Si le nœud à supprimer a zéro ou 1 enfant, alors la méthode de suppression "suivra le chemin" de la racine à ce nœud. Ainsi, le pire moment est proportionnel à la hauteur de l'arbre, à la fois pour la recherche et l'insertion.
Si le nœud à supprimer a deux enfants, les étapes suivantes sont suivies:
- Trouvez le nœud à supprimer en suivant le chemin depuis la racine jusqu'à celui-ci.
- Trouvez la plus petite valeur de v dans le sous-arbre de droite, en continuant le long du chemin vers la feuille.
- Supprimez récursivement la valeur de v, suivez le même chemin qu'à l'étape 2.
- Ainsi, dans le pire des cas, le chemin de la racine à la feuille est effectué deux fois.
Ordre des traversées
Traversal est un processus qui visite tous les nœuds d'un arbre. Parce qu'un arbre de recherche binaire C est une structure de données non linéaire, il n'y a pas de parcours unique. Par exemple, parfois plusieurs algorithmes de parcoursregroupés dans les deux types suivants:
- profondeur de franchissement;
- première passe.
Il n'y a qu'un seul type de croisement de largeur - en contournant le niveau. Cette traversée visite les nœuds de niveau inférieur et gauche, supérieur et droit.
Il existe trois différents types de passages en profondeur:
- Passer la précommande - visitez d'abord le parent, puis l'enfant gauche et droit.
- Passing InOrder - visiter l'enfant de gauche, puis le parent et l'enfant de droite.
- Passer le PostOrder - visiter l'enfant de gauche, puis l'enfant de droite, puis le parent.
Exemple pour quatre parcours d'un arbre de recherche binaire:
- Précommande - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- Dans l'ordre - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- NiveauOrdre - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
La figure montre l'ordre dans lequel les nœuds sont visités. Le nombre 1 est le premier nœud d'un parcours particulier et 7 est le dernier nœud.
Ces traversées générales peuvent être représentées comme un seul algorithme, en supposant que chaque nœud est visité trois fois. La visite d'Euler est une promenade autour d'un arbre binaire où chaque arête est traitée comme un mur que l'utilisateur ne peut pas franchir. Dans cette promenade, chaque nœud sera visité soit à gauche, soit en bas, soit à droite. Le tour d'Euler, qui visite les nœuds de gauche, provoque le contournement de la préposition. Lorsque les nœuds ci-dessous sont visités, ils sont traversés dans l'ordre. Et lorsque les nœuds de droite sont visités - obtenezcontournement pas à pas.
Navigation et débogage
Pour faciliter la navigation dans l'arborescence, créez des fonctions qui vérifient d'abord s'il s'agit de l'enfant gauche ou droit. Pour modifier la position d'un nœud, il doit y avoir un accès facile au pointeur au niveau du nœud parent. Implémenter correctement un arbre est très difficile, vous devez donc connaître et appliquer les processus de débogage. Un arbre de recherche binaire avec une implémentation a souvent des pointeurs qui n'indiquent pas réellement la direction du voyage.
Pour comprendre tout cela, une fonction est utilisée qui vérifie si l'arbre peut être correct et aide à trouver de nombreuses erreurs. Par exemple, il vérifie si le nœud parent est un nœud enfant. Avec assert(is_wellformed(root)) de nombreuses erreurs peuvent être détectées prématurément. En utilisant quelques points d'arrêt donnés dans cette fonction, vous pouvez également déterminer exactement quel pointeur est erroné.
Function Konsolenausgabe
Cette fonction vide toute l'arborescence de la console et est donc très utile. L'ordre dans lequel l'objectif de sortie de l'arborescence est exécuté est:
- Pour ce faire, vous devez d'abord déterminer quelles informations seront sorties via le nœud.
- Et vous devez également connaître la largeur et la hauteur de l'arbre pour tenir compte de l'espace à laisser.
- Les fonctions suivantes calculent ces informations pour l'arbre et chaque sous-arbre. Comme vous ne pouvez écrire sur la console que ligne par ligne, vous devrez également imprimer l'arborescence ligne par ligne.
- Maintenant, nous avons besoin d'un autre moyen de retraitl'arbre entier, pas seulement ligne par ligne.
- Avec l'aide de la fonction de vidage, vous pouvez lire l'arborescence et améliorer considérablement l'algorithme de sortie, en ce qui concerne la vitesse.
Cependant, cette fonction sera difficile à utiliser sur les grands arbres.
Copier le constructeur et le destructeur
Parce qu'un arbre n'est pas une structure de données triviale, il est préférable d'implémenter un constructeur de copie, un destructeur et un opérateur d'affectation. Le destructeur est facile à implémenter de manière récursive. Pour les très grands arbres, il peut gérer le "débordement de tas". Dans ce cas, il est formulé de manière itérative. L'idée est de supprimer la feuille représentant la plus petite valeur de toutes les feuilles, donc c'est sur le côté gauche de l'arbre. Couper les premières feuilles en crée de nouvelles et l'arbre se rétrécit jusqu'à ce qu'il cesse finalement d'exister.
Le constructeur de copie peut également être implémenté de manière récursive, mais soyez prudent si une exception est levée. Sinon, l'arbre devient rapidement déroutant et sujet aux erreurs. C'est pourquoi la version itérative est privilégiée. L'idée est de parcourir l'ancien arbre et le nouvel arbre, comme vous le feriez dans le destructeur, en clonant tous les nœuds qui se trouvent dans l'ancien arbre mais pas les nouveaux.
Avec cette méthode, l'implémentation de l'arbre de recherche binaire est toujours dans un état sain et peut être supprimée par le destructeur même dans un état incomplet. Si une exception se produit, tout ce que vous avez à faire est de demander au destructeur de supprimer l'arbre semi-fini. opérateur d'assignationpeut être facilement mis en œuvre à l'aide de Copy & Swap.
Création d'un arbre de recherche binaire
Les arbres de recherche binaires optimaux sont incroyablement efficaces s'ils sont gérés correctement. Quelques règles pour les arbres de recherche binaire:
- Un nœud parent a au plus 2 nœuds enfants.
- Le nœud enfant gauche est toujours inférieur au nœud parent.
- Un nœud enfant valide est toujours supérieur ou égal au nœud parent.
Le tableau qui sera utilisé pour construire l'arbre binaire de recherche:
- Un tableau d'entiers de base de sept valeurs dans un ordre non trié.
- La première valeur du tableau est 10, donc la première étape dans la construction de l'arbre est de créer un nœud racine 10, comme montré ici.
- Avec un ensemble de nœuds racine, toutes les autres valeurs seront des enfants de ce nœud. En se référant aux règles, la première étape à suivre pour ajouter 7 à l'arbre est de le comparer au nœud racine.
- Si la valeur 7 est inférieure à 10, il deviendra le nœud enfant gauche.
- Si la valeur 7 est supérieure ou égale à 10, elle se déplacera vers la droite. Puisque 7 est connu pour être inférieur à 10, il est désigné comme le nœud enfant gauche.
- Effectuer des comparaisons récursives pour chaque élément.
- En suivant le même schéma, effectuez la même comparaison avec la 14e valeur du tableau.
- Comparer la valeur 14 au nœud racine 10, sachant que 14 est le bon enfant.
- En parcourant le tableau,venez à 20.
- Commencez par comparer le tableau avec 10, celui qui est le plus grand. Alors déplacez-vous vers la droite et comparez-le à 14, il a plus de 14 ans et n'a pas d'enfants à droite.
- Maintenant, il y a une valeur de 1. En suivant le même schéma que les autres valeurs, comparez 1 à 10, en vous déplaçant vers la gauche et en comparant à 7 et enfin au 1 enfant gauche du 7ème nœud.
- Si la valeur est 5, comparez-la à 10. Comme 5 est inférieur à 10, passez à gauche et comparez-la à 7.
- Sachant que 5 est inférieur à 7, continuez dans l'arbre et comparez 5 avec 1 valeur.
- Si 1 n'a pas d'enfant et que 5 est supérieur à 1, alors 5 est un enfant valide de 1 nœud.
- Insérez enfin la valeur 8 dans l'arborescence.
- Quand 8 est inférieur à 10, déplacez-le vers la gauche et comparez-le à 7, 8 est supérieur à 7, alors déplacez-le vers la droite et complétez l'arbre, faisant de 8 un enfant de 7.
Obtenir et évaluer l'élégance simple des arbres de recherche binaires optimaux. Comme de nombreux sujets de programmation, la puissance des arbres de recherche binaires provient de leur capacité à résoudre les données en petits composants liés. À partir de maintenant, vous pouvez travailler avec l'ensemble de données complet de manière organisée.
Problèmes potentiels de recherche binaire
Les arbres de recherche binaires sont excellents, mais il y a quelques mises en garde à garder à l'esprit. Ils ne sont généralement efficaces que s'ils sont équilibrés. Un arbre équilibré est un arbre dans lequella différence entre les hauteurs des sous-arbres de n'importe quel nœud de l'arbre est d'au plus un. Prenons un exemple qui pourrait aider à clarifier les règles. Imaginons que le tableau commence par être triable.
Si vous essayez d'exécuter un algorithme d'arbre de recherche binaire sur cet arbre, il fonctionnera exactement comme s'il parcourait simplement le tableau jusqu'à ce que la valeur souhaitée soit trouvée. La puissance de la recherche binaire réside dans sa capacité à filtrer rapidement les valeurs indésirables. Lorsqu'un arbre n'est pas équilibré, il ne fournira pas les mêmes avantages qu'un arbre équilibré.
Il est très important d'examiner les données avec lesquelles l'utilisateur travaille lors de la création d'un arbre de recherche binaire. Vous pouvez intégrer des routines telles que la randomisation de tableaux avant d'implémenter un arbre de recherche binaire pour les entiers afin de l'équilibrer.
Exemples de calcul de recherche binaire
Nous devons déterminer quel type d'arbre résultera si 25 est inséré dans l'arbre de recherche binaire suivant:
10
/
/
5 15
/ /
/ /
2 12 20
Lors de l'insertion de x dans un arbre T qui ne contient pas encore x, la clé x est toujours placée dans une nouvelle feuille. En relation avec cela, le nouvel arbre ressemblera à:
10
/
/
5 15
/ /
/ /
2 12 20
25
Quel type d'arbre obtiendriez-vous si vous insériez 7 dans l'arbre de recherche binaire suivant ?
10
/
/
5 15
/ /
/ /
2 12 20
Réponse:
10
/
/
/
5 15
/ / /
/ / /
2 7 12 20
Un arbre de recherche binaire peut être utilisé pour stocker n'importe quel objet. L'avantage d'utiliser un arbre de recherche binaire au lieu d'une liste chaînée est que si l'arbre est raisonnablement équilibré et ressemble plus à un arbre "complet" qu'à un arbre "linéaire", les opérations d'insertion, de recherche et de suppression peuvent être implémentées pour s'exécuter dans Temps O(log N).
