Introduction détaillée aux arbres de recherche binaires en python (exemple de code)

Cet article vous apporte une introduction détaillée (exemple de code) sur les arbres de recherche binaires en python. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

1. Arbre de recherche binaire

**Arbre de recherche binaire (recherche binaire BST tree)** est un arbre binaire spécial. La valeur de n'importe quel nœud est supérieure à la valeur de l'enfant de gauche et inférieure ou égale à la valeur de l'enfant de droite (binaire) est parcourue dans l'ordre. Search Tree) peut obtenir un ensemble trié d'éléments, et la consommation de temps d'insertion et de suppression est également relativement raisonnable, mais un inconvénient est que la surcharge de mémoire est un peu importante.

Propriétés des arbres de recherche binaires

1 Pour tout nœud x, la clé dans son sous-arbre gauche n'est pas supérieure à x.key, et la clé dans son sous-arbre droit n'est pas inférieure à x. .clé.
2. Différents arbres de recherche binaires peuvent représenter le même ensemble de valeurs.
3. Les opérations de base d'un arbre de recherche binaire sont proportionnelles à la hauteur de l'arbre, donc s'il s'agit d'un arbre binaire complet, le pire temps d'exécution est Θ(lgn), mais s'il s'agit d'un arbre linéaire connecté par n nœuds, alors le pire temps d’exécution est Θ(n).
4. Le nœud racine est le seul nœud dont le pointeur parent pointe vers le nœud NIL.
5. Chaque nœud comprend au moins quatre attributs : clé, gauche, droite et parent Lors de la construction d'un arbre de recherche binaire, il doit y avoir un algorithme de comparaison pour la clé.

2. Implémentation de l'arbre de recherche binaire

1 Définir les nœuds de l'arbre

:

class TreeNode:
    def __init__(self,key,val,left=None,right=None,parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent
        
class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.size = 0

2. . Insérer

Maintenant que nous avons le shell BinarySearchTree et TreeNode, il est temps d'écrire la méthode put, qui nous permettra de construire un arbre de recherche binaire. La méthode put est une méthode de la classe BinarySearchTree. Cette méthode vérifiera si l'arbre a déjà une racine. S'il n'y a pas de racine, put créera un nouveau TreeNode et en fera la racine de l'arborescence. Si le nœud racine est déjà en place, put appelle la fonction d'assistance récursive privée _put pour rechercher l'arbre selon l'algorithme suivant :

• En partant de la racine de l'arbre, recherchez le binaire arbre, faisant correspondre la nouvelle clé avec les clés de nœud actuelles à comparer. Si la nouvelle clé est plus petite que le nœud actuel, le sous-arbre gauche est recherché. Si la nouvelle clé est supérieure au nœud actuel, le sous-arbre de droite est recherché.

• Lorsqu'il n'y a pas d'enfant gauche (ou droit) à rechercher, on trouve la position dans l'arborescence où le nouveau nœud doit être établi.

• Pour ajouter un nœud à l'arborescence, créez un nouvel objet TreeNode et insérez l'objet dans le nœud découvert à l'étape précédente.
  Lors de l'insertion, il est toujours inséré dans l'arbre en tant que nœud feuille
  Étant donné une séquence pour construire un arbre de recherche binaire en séquence, l'arbre de recherche binaire est unique si toutes les clés de celui-ci ; séquence sont utilisées. Les mots sont utilisés pour construire des arbres binaires possibles (disposés dans n'importe quel ordre), qui ne sont généralement pas uniques.

def put(self,key,val):
    if self.root:
        self._put(key,val,self.root)
    else:
        self.root = TreeNode(key,val)
    self.size = self.size + 1

def _put(self,key,val,currentNode):
    if key < currentNode.key:
        if currentNode.hasLeftChild():
               self._put(key,val,currentNode.leftChild)
        else:
               currentNode.leftChild = TreeNode(key,val,parent=currentNode)
    else:
        if currentNode.hasRightChild():
               self._put(key,val,currentNode.rightChild)
        else:
               currentNode.rightChild = TreeNode(key,val,parent=currentNode)

Ce qui précède montre le code Python pour insérer un nouveau nœud dans l'arborescence. La fonction _put est écrite de manière récursive en suivant les étapes ci-dessus. Notez que lorsqu'un nouveau nœud enfant est inséré dans l'arborescence, currentNode est transmis au nouveau nœud de l'arborescence en tant que nœud parent.
Un problème important dans notre implémentation de l'insertion est que les clés en double ne peuvent pas être gérées correctement. Lorsque notre arbre est implémenté, une clé en double créera un nouveau nœud avec la même valeur de clé dans le sous-arbre droit du nœud avec la clé d'origine. Le résultat est que le nœud avec la nouvelle clé ne sera jamais trouvé lors de la recherche. Une meilleure façon de gérer l’insertion d’une clé en double consiste à remplacer l’ancienne valeur par la valeur associée à la nouvelle clé.

3. Rechercher

Une fois l'arborescence construite, la tâche suivante consiste à implémenter la récupération de la valeur d'une clé donnée. La méthode get est plus simple que la méthode put car elle recherche simplement l'arborescence de manière récursive jusqu'à ce qu'elle atteigne un nœud feuille non correspondant ou trouve une clé correspondante. Lorsqu'une clé correspondante est trouvée, la valeur stockée dans la charge utile du nœud est renvoyée.

Lorsque l'arbre de recherche binaire n'est pas vide :

• Comparez d'abord la valeur donnée avec le mot-clé du nœud racine. S'ils sont égaux, la recherche est réussie<.>

• S'il est inférieur à la valeur du mot-clé du nœud racine, recherchez récursivement le sous-arbre de gauche

• S'il est supérieur à la valeur du mot-clé de le nœud racine, recherchez récursivement le sous-arbre droit

• Si le sous-arbre est vide, la recherche échoue

def get(self,key):
    if self.root:
        res = self._get(key,self.root)
        if res:
               return res.payload
        else:
               return None
    else:
        return None

def _get(self,key,currentNode):
    if not currentNode:
        return None
    elif currentNode.key == key:
        return currentNode
    elif key < currentNode.key:
        return self._get(key,currentNode.leftChild)
    else:
        return self._get(key,currentNode.rightChild)

def __getitem__(self,key):
    return self.get(key)

4. la

première tâche Elle parcourt l'arborescence pour trouver le nœud à supprimer. Si l'arborescence comporte plusieurs nœuds, nous recherchons à l'aide de la méthode _get le TreeNode qui doit être supprimé. Si l'arborescence n'a qu'un seul nœud, cela signifie que nous supprimons la racine de l'arborescence, mais nous devons quand même vérifier que la clé de la racine correspond à la clé que nous voulons supprimer. Dans les deux cas, l'opérateur del générera une erreur si la clé n'est pas trouvée.

def delete(self,key):
   if self.size > 1:
      nodeToRemove = self._get(key,self.root)
      if nodeToRemove:
          self.remove(nodeToRemove)
          self.size = self.size-1
      else:
          raise KeyError('Error, key not in tree')
   elif self.size == 1 and self.root.key == key:
      self.root = None
      self.size = self.size - 1
   else:
      raise KeyError('Error, key not in tree')

def __delitem__(self,key):
    self.delete(key)

Une fois que nous avons trouvé le nœud de la clé que nous voulons supprimer, nous devons considérer trois situations :

• Le nœud à supprimer n'a pas d'enfant.

• Le nœud à supprimer n'a qu'un seul nœud enfant.

• Le nœud à supprimer a deux nœuds enfants.

第一种情况：
如果当前节点没有子节点，我们需要做的是删除节点并删除对父节点中该节点的引用。
第二种情况：
如果一个节点只有一个孩子，那么我们可以简单地促进孩子取代其父。此案例的代码展示在下一个列表中。当你看这个代码，你会看到有六种情况要考虑。由于这些情况相对于左孩子或右孩子对称，我们将仅讨论当前节点具有左孩子的情况。决策如下：

• 如果当前节点是左子节点，则我们只需要更新左子节点的父引用以指向当前节点的父节点，然后更新父节点的左子节点引用以指向当前节点的左子节点。

• 如果当前节点是右子节点，则我们只需要更新左子节点的父引用以指向当前节点的父节点，然后更新父节点的右子节点引用以指向当前节点的左子节点。

• 如果当前节点没有父级，则它是根。在这种情况下，我们将通过在根上调用replaceNodeData 方法来替换 key，payload，leftChild 和 rightChild 数据。
  第三种情况：
  最难处理的情况。 如果一个节点有两个孩子，那么我们不太可能简单地提升其中一个节点来占据节点的位置。 然而，我们可以在树中搜索可用于替换被调度删除的节点的节点。 我们需要的是一个节点，它将保留现有的左和右子树的二叉搜索树关系。 执行此操作的节点是树中具有次最大键的节点。 我们将这个节点称为后继节点，我们将看一种方法来很快找到后继节点。 继承节点保证没有多于一个孩子，所以我们知道使用已经实现的两种情况删除它。 一旦删除了后继，我们只需将它放在树中，代替要删除的节点。
  找到后继的代码如下所示，是 TreeNode 类的一个方法。此代码利用二叉搜索树的相同属性，采用中序遍历从最小到最大打印树中的节点。在寻找接班人时，有三种情况需要考虑：

• 如果节点有右子节点，则后继节点是右子树中的最小的键。

• 如果节点没有右子节点并且是父节点的左子节点，则父节点是后继节点。

• 如果节点是其父节点的右子节点，并且它本身没有右子节点，则此节点的后继节点是其父节点的后继节点，不包括此节点。

def findSuccessor(self):
    succ = None
    if self.hasRightChild():
        succ = self.rightChild.findMin()
    else:
        if self.parent:
               if self.isLeftChild():
                   succ = self.parent
               else:
                   self.parent.rightChild = None
                   succ = self.parent.findSuccessor()
                   self.parent.rightChild = self
    return succ

def findMin(self):
    current = self
    while current.hasLeftChild():
        current = current.leftChild
    return current

def spliceOut(self):
    if self.isLeaf():
        if self.isLeftChild():
               self.parent.leftChild = None
        else:
               self.parent.rightChild = None
    elif self.hasAnyChildren():
        if self.hasLeftChild():
               if self.isLeftChild():
                  self.parent.leftChild = self.leftChild
               else:
                  self.parent.rightChild = self.leftChild
               self.leftChild.parent = self.parent
        else:
               if self.isLeftChild():
                  self.parent.leftChild = self.rightChild
               else:
                  self.parent.rightChild = self.rightChild
               self.rightChild.parent = self.parent

三、平衡二叉搜索树（AVL树）

1. 概念

二叉搜索树的深度越小，那么搜索所需要的运算时间越小。一个深度为log(n)的二叉搜索树，搜索算法的时间复杂度也是log(n)。然而，我们在二叉搜索树中已经实现的插入和删除操作并不能让保持log(n)的深度。如果我们按照8，7，6，5，4，3，2，1的顺序插入节点，那么就是一个深度为n的二叉树。那么，搜索算法的时间复杂度为n。
在上一节中我们讨论了建立一个二叉搜索树。我们知道，当树变得不平衡时get和put操作会使二叉搜索树的性能降低到O(n)。
如何减少树的深度呢？
一种想法是先填满一层，再去填充下一层，这样就是一个完全二叉树(complete binary tree)。这样的二叉树实现插入算法会比较复杂。另一种比较容易实现的树状数据结构——AVL树，其搜索算法复杂度为log(n)。
在这一节中我们将看到一种特殊的二叉搜索树，它可以自动进行调整，以确保树随时都保持平衡。这种树被称为AVL树，命名源于其发明者：G.M. Adelson-Velskii 和 E.M. Landis。

Implémentation de l'arbre AVL Le type de données abstrait Map est comme un arbre de recherche binaire ordinaire, la seule différence est la façon dont l'arbre est exécuté. Afin de mettre en œuvre notre arbre AVL, nous devons garder une trace du facteur d'équilibrage pour chaque nœud de l'arborescence. Pour ce faire, nous examinons les hauteurs des sous-arbres gauche et droit de chaque nœud. Plus formellement, nous définissons le facteur d'équilibre d'un nœud comme la différence entre la hauteur du sous-arbre gauche et la hauteur du sous-arbre droit.
balanceFac tor=height(leftSub Tree)−height(right SubTree)En utilisant la définition du facteur d'équilibre donnée ci-dessus, nous disons qu'un sous-arbre est lourd à gauche si le facteur d'équilibre est supérieur à zéro . Si le facteur d'équilibre est inférieur à zéro, le sous-arbre est lourd à droite. Si le facteur d’équilibre est nul, alors l’arbre est parfaitement équilibré. Afin de mettre en œuvre un arbre AVL et de bénéficier des avantages d'un arbre équilibré, nous définirons l'équilibrage de l'arbre si le facteur d'équilibrage est de -1,0 ou 1. Une fois que le facteur d’équilibre d’un nœud de l’arbre est en dehors de cette plage, nous aurons besoin d’une procédure pour rééquilibrer l’arbre.

Le nombre de nœuds (Nh) d'un arbre de hauteur h est :

Nh=1+Nh−1+Nh−2 Cette formule est très similaire à la suite de Fibonacci. Nous pouvons utiliser cette formule pour déduire la hauteur d'un arbre AVL à partir du nombre de nœuds dans l'arbre. À mesure que les nombres de la séquence de Fibonacci deviennent de plus en plus grands, Fi/Fi−1 se rapproche de plus en plus du nombre d'or Φ
À tout moment, la hauteur de notre arbre AVL est égale à une constante qui est le logarithme du nombre de nœuds dans l’arbre (1,44) fois. C'est une bonne nouvelle pour la recherche dans notre arborescence AVL car elle limite la recherche à O(logN).

2. Implémentation

Lorsqu'un nouveau nœud est ajouté, il détruira l'équilibre de l'arbre binaire, il doit donc être corrigé par rotation.

Rotation simple

Pour effectuer une rotation correcte à droite, nous devons procéder comme suit :

• Créer le nœud gauche Devient la racine du sous-arbre.

• Déplacez l'ancienne racine vers le nœud droit de la nouvelle racine.

• Si la nouvelle racine avait à l'origine un nœud droit, faites-en le nœud gauche du nœud droit de la nouvelle racine.

Remarque : Puisque la nouvelle racine est le nœud gauche de l'ancienne racine, le nœud gauche de l'ancienne racine après le mouvement doit être vide. À ce stade, vous pouvez ajouter directement le nœud gauche à l’ancienne racine déplacée.

De même, pour effectuer une rotation à gauche, nous devons procéder comme suit :

• Faire du nœud droit (B) la racine du sous-arbre.

• Déplacez l'ancien nœud racine (A) vers le nœud gauche de la nouvelle racine.

• Si la nouvelle racine (B) a à l'origine un nœud gauche, alors laissez le nœud gauche du B d'origine devenir le nœud droit du nouveau nœud racine gauche (A).

Double rotation

Comme le montre la figure, si le nœud enfant est 4 au lieu de 2, essayez une rotation simple et vous constaterez que le problème ne peut pas être résolu.
Pour résoudre ce problème, nous devons utiliser les règles suivantes :

• Si le sous-arbre doit être tourné vers la gauche pour le rendre équilibré, vérifiez d'abord le facteur d'équilibre du nœud droit. Si le nœud droit est lourd à gauche, le nœud droit pivote vers la droite, puis le nœud d'origine pivote vers la gauche.

• Si le sous-arbre doit être tourné vers la droite pour le rendre équilibré, vérifiez d'abord le facteur d'équilibre du nœud gauche. Si le nœud gauche est lourd à droite, le nœud gauche pivote vers la gauche, puis le nœud d'origine pivote vers la droite.

La solution à l'heure actuelle est la double rotation.

La double rotation est en fait deux rotations simples : le sous-arbre avec le nœud racine 4 effectue d'abord une simple rotation vers la gauche, puis le sous-arbre avec le nœud racine 5 effectue une rotation vers la droite d'une seule rotation. Cela restaure les propriétés ACL de l'arborescence.

Pour les arbres AVL, il peut être prouvé que lorsqu'un nouveau nœud est ajouté, les propriétés de l'arbre AVL peuvent toujours être restaurées en une seule rotation.

Règles de rotation

Lorsque nous insérons un nouveau nœud, où tourne-t-il ? Devons-nous utiliser une rotation simple ou une rotation double ?

Nous suivons les étapes de base suivantes :

1. Ajouter des nœuds selon la méthode de l'arbre de recherche binaire, et la nouvelle Le nœud est appelé un nœud feuille.

2. Commencez à partir du nœud nouvellement ajouté et remontez jusqu'au premier nœud déséquilibré (5).
   (Si vous remontez jusqu'au nœud racine et qu'il n'y a pas de nœud déséquilibré, cela signifie que l'arbre est déjà conforme à la propriété AVL.)

3. Trouvez le bord cassé (5 ->3), et Déterminez la direction de la corde cassée (côté gauche de 5)

4. En prenant l'extrémité inférieure du bord cassé (3) comme nœud racine, déterminez lequel des deux sous-arbres a la plus grande profondeur (sous-arbre gauche ou sous-arbre droit Arbre).
   (La profondeur des deux sous-arbres ne peut pas être égale et le sous-arbre avec une plus grande profondeur contient de nouveaux nœuds.)

5. Si les directions des étapes 2 et 3 sont les mêmes ( les deux à gauche ou les deux à droite) nécessite une seule rotation du sous-arbre avec le nœud déséquilibré comme nœud racine.

6. Sinon, faites une double rotation du sous-arbre enraciné au nœud déséquilibré.

4. Arbre rouge-noir

L'arbre rouge-noir est un arbre de recherche binaire équilibré couramment utilisé. Il est complexe, mais son fonctionnement a de bons résultats d'optimisation. Le temps d'exécution dans le mauvais cas, c'est-à-dire la complexité de l'opération, ne se détériore pas et est efficace en pratique : il peut effectuer une seule recherche, insertion et suppression en un temps O(logn), où n est le nombre d'éléments dans l'arborescence. nombre.
L'arbre rouge-noir est un arbre de recherche équilibré très intéressant. Ses performances statistiques sont meilleures que l'arbre binaire équilibré (AVL-tree), c'est pourquoi l'arbre rouge-noir est utilisé dans de nombreux endroits. En C++ STL, de nombreuses parties (y compris actuellement set, multiset, map, multimap) appliquent des variations de l'arbre rouge-noir (l'arbre rouge-noir dans SGI STL a quelques changements, Ces modifications offrent de meilleures performances, ainsi qu'une prise en charge des opérations d'ensemble).
Les règles principales pour les arbres rouge-noir :
Les règles principales pour les arbres rouge-noir sont les suivantes :

1. Les nœuds sont rouges ou noirs.

2. La racine est noire.

3. Toutes les feuilles sont noires (les feuilles sont des nœuds NIL).

4. Chaque nœud rouge doit avoir deux nœuds enfants noirs. (Il ne peut pas y avoir deux nœuds rouges consécutifs sur un chemin allant de chaque feuille à la racine.)

5. Tous les chemins simples d'un nœud à chacune de ses feuilles contiennent le même numéro de nœud noir.

Les nœuds insérés dans l'arbre rouge-noir sont tous rouges. Ce n'est pas accidentel, car l'insertion d'un nœud rouge est moins susceptible de violer la règle rouge-noir que l'insertion d'un nœud noir. La raison est la suivante : l'insertion d'un nœud noir modifiera toujours la hauteur du noir (en violation de la règle 4), mais l'insertion d'un nœud rouge n'a qu'une demi-chance de violer la règle 3. De plus, une violation de la règle 3 est plus facile à corriger qu’une violation de la règle 4.
Lors de l'insertion d'un nouveau nœud, cet équilibre peut être détruit. L'arbre rouge-noir corrige principalement l'équilibre de trois manières, en changeant la couleur du nœud, la rotation à gauche et la rotation à droite. (Règles spécifiques omises)
Parce que chaque arbre rouge-noir est également un arbre de recherche binaire spécialisé, les opérations en lecture seule sur l'arbre rouge-noir sont les mêmes que les opérations en lecture seule sur l'arbre de recherche binaire ordinaire. Cependant, les opérations d'insertion et de suppression sur un arbre rouge-noir ne respecteront plus les propriétés d'un arbre rouge-noir. La restauration des propriétés d'un arbre rouge-noir nécessite un petit changement de couleur (O(logn)) (en fait très rapide) et pas plus de trois rotations d'arbre (deux pour les opérations d'insertion). Bien que l'insertion et la suppression soient complexes, le temps d'opération peut toujours être conservé sous forme de temps O(logn).
La hauteur d'un arbre rouge-noir à n nœuds internes est d'au plus 2lg(n+1).

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!