La relation entre les arbres binaires équilibrés et les arbres binaires triés

Il n'y a pas de relation directe entre les arbres binaires équilibrés et les arbres de tri binaire, mais l'efficacité de recherche des arbres de tri binaire est liée à la forme de l'arbre binaire, donc quand nous voulons que la forme de l'arbre de tri binaire être uniforme, comme ceci. Les arbres binaires sont appelés arbres binaires équilibrés.

1.

Arbre de tri binaire, également connu sous le nom de

Arbre de recherche binaire (Arbre de recherche binaire), également connu sous le nom de Arbre de recherche binaire.

• Définition de l'arbre de tri binaire :

Un arbre de tri binaire est soit un arbre vide, soit a les propriétés suivantes Arbre binaire :

Si le sous-arbre de gauche n'est pas vide, alors les valeurs de tous les nœuds du sous-arbre de gauche sont inférieures à la valeur de son nœud racine
1. Si le sous-arbre de droite l'est ; pas vide, alors Les valeurs de tous les nœuds du sous-arbre droit sont supérieures à la valeur de son nœud racine
2. Les sous-arbres gauche et droit sont également respectivement des arbres triés binaires ;

Comme le montre la figure ci-dessous, il s'agit d'un arbre de tri binaire :

Effectuez un parcours dans l'ordre de l'arbre de tri binaire pour obtenir une séquence triée par mot-clé, par exemple, un parcours dans l'ordre de la figure ci-dessus peut obtenir une séquence ordonnée : 10, 42, 45, 55, 58, 63, 67, 70, 83, 90, 98

• Analyse de recherche de l'arbre de tri binaire

En termes de performance temporelle moyenne de la recherche, la recherche sur l'arbre de tri binaire est similaire à la recherche binaire, mais en termes de maintien du ordre de la table En termes d'efficacité, l'arbre trié binaire est plus efficace car il n'a pas besoin de déplacer de nœuds et n'a besoin que de modifier le pointeur pour terminer les opérations d'insertion et de suppression de l'arbre trié binaire.

Recherche d'arbre trié binaire Dans le pire des cas, le temps de recherche requis dépend de la profondeur de l'

arbre :

1. Lorsqu'un arbre de tri binaire est proche d'un arbre binaire complet , sa profondeur est $log_2n$ , donc le temps de recherche dans le pire des cas est O( $log_2n$ ), qui est du même ordre de grandeur que la recherche binaire.
2. Lorsqu'un arbre binaire forme un arbre à branche unique comme le montre la figure ci-dessous, sa profondeur est n, et le temps de recherche dans le pire des cas est O(n), ce qui est du même ordre de grandeur que la recherche séquentielle.
   
   DoncAfin d'assurer une vitesse de recherche élevée pour la recherche d'arbre de tri binaire, nous espérons que l'arbre binaire est proche d'un arbre binaire complet, ou que les profondeurs des sous-arbres gauche et droit de chaque nœud de l'arbre binaire est aussi égal que possible

2. Arbre binaire équilibré

Grâce à l'analyse ci-dessus, on peut voir que l'efficacité de la recherche du binaire. L'arbre de tri est lié à la forme de l'arbre binaire. Nous espérons que la forme de l'arbre de tri binaire est uniforme, un tel arbre binaire est appelé arbre binaire équilibré.

• Définition de l'arbre binaire équilibré
  Arbre binaire équilibré (Balanced Binary Tree), c'est un arbre vide, ou possède les propriétés suivantes :

1. La valeur absolue de la différence de profondeur entre ses sous-arbres gauche et droit ne dépasse pas 1
2. Ses sous-arbres gauche et droit sont également respectivement des arbres binaires équilibrés ;

La profondeur du sous-arbre gauche d'un nœud d'arbre binaire moins la profondeur de son sous-arbre droit est appelée le facteur d'équilibre BF, il n'est alors possible d'équilibrer que les facteurs d'équilibre de tous les nœuds de l'arbre binaire Ils sont -1, 0 et 1. Celui de gauche dans la figure ci-dessous est un arbre binaire équilibré, et celui de droite est un arbre binaire déséquilibré.

Étant donné que la différence entre les profondeurs des sous-arbres gauche et droit de n'importe quel nœud sur un arbre binaire équilibré ne dépassera pas 1, on peut prouver que sa profondeur est la même que la profondeur d'un arbre binaire complet. arbre binaire à n nœuds $lfloor log_2n rfloor$+1 sont identiques ordre de grandeur. Par conséquent, son nombre moyen de recherches est également de >g2$o$g

• Il existe généralement quatre situations pour ajuster le sous-arbre déséquilibré minimum :

1. Rotation unidirectionnelle à droite (type LL) : Insérez le sous-arbre gauche dont la position est le sous-arbre gauche et effectuez une seule rotation vers la droite avec le sous-arbre gauche comme axe, comme indiqué dans la figure ci-dessous. Le nombre à côté du nœud est le facteur d'équilibre du nœud, et le nœud I est le nœud actuellement inséré (si le nœud I est au milieu, cela signifie que le nœud I peut être soit un enfant de gauche, soit un enfant de droite.

Notez le type LL, tournez avec le nœud du milieu comme axe. Pourquoi ici I est l'enfant gauche de BL et B-BL-I ne peut pas être utilisé comme type LL , car le nœud A est le équilibre le plus proche du nœud I. Pour le sous-arbre avec une valeur absolue du facteur > 1 , la valeur absolue du facteur d'équilibre des autres nœuds ne dépasse pas 1 de la même manière, lorsque I est ; l'enfant droit de BL, B-BL-I ne peut pas être considéré comme de type LR
2
Rotation unidirectionnelle à gauche (type RR) : La position d'insertion est le sous-arbre droit du sous-arbre droit, et le sous-arbre droit est l'axe, et une seule opération est effectuée Rotation à gauche Faites attention au type RR Rotation avec le milieu. nœud car l'axe n'affecte pas le type RR réel.

3. Rotation bidirectionnelle d'abord à gauche puis à droite (type LR) : insérez le sous-arbre droit dont la position est le sous-arbre gauche, et effectuez deux rotations, d'abord vers la gauche puis vers la droite
Insérez le nœud comme enfant de gauche : Notez pourquoi

ne peut pas utiliser B-C-I comme sous-arbre pour le définir comme type RL . Le principe est le même que l'explication du type RR. Pour le type LR, l'extrémité R ou L est proche de l'extrémité du nœud inséré comme axe de rotation (comme le montre la figure ci-dessous, cela équivaut à faire d'abord tourner le sous-arbre. avec B comme racine, puis rotation du sous-arbre avec A comme racine, puis rotation du sous-arbre avec A comme racine Enfant :

4
Rotation bidirectionnelle d'abord). à droite puis à gauche (type RL) : insérez le sous-arbre gauche dont la position est le sous-arbre droit, et effectuez deux ajustements, d'abord la rotation à droite puis la rotation à gauche ; La situation de traitement est similaire à LR ; Insérer le nœud comme enfant de gauche :

Insérer le nœud comme enfant de droite :
à travers ce qui précède, nous pouvons constater que le facteur d'équilibre a une excellente relation avec le. type

doit utiliser le nœud le plus proche du nœud inséré et la valeur absolue du facteur d'équilibre > 1 comme sous-arbre du nœud racine pour déterminer de quel type

il s'agit

Pratique

Comme le montre la figure ci-dessous, insérez d'abord le nœud 2 pour devenir un type LL, puis équilibrez-le après le traitement global à droite >. Après avoir inséré 8 et 6 dans l'ordre, la valeur absolue du facteur d'équilibre du nœud 5 est >1, devenant un type RL, utilisez donc d'abord 5 comme nœud racine et faites pivoter à droite son sous-arbre 8-6 (devenant RR Tapez), puis faites pivoter l'arbre entier avec 5 comme nœud racine vers la gauche. Après avoir continué à insérer le nœud 9, le facteur d'équilibre du nœud 4 est >1, devenant le type RR, donc 4 est le nœud racine, tournez. le tout à gauche.

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!