[Introduction] J'ai essayé de l'implémenter moi-même tout en expliquant l'arbre de dichotomie

Objectif

Je souhaite approfondir ma compréhension des structures de données et des algorithmes en apprenant l'arbre de dichotomie.
Implémenter un arbre de dichotomie et une structure de données en python.
Cela peut être plus facile à mettre en œuvre si la structure de données est pliée dans une liste unidimensionnelle, mais afin d'approfondir la compréhension de la structure de données de l'arbre, nous osons définir une classe de nœuds et implémenter un arbre de dichotomie.

Contenu

Définition de l'arbre dichotomisé

Un arbre de dichotomie est une structure de données de dichotomie qui contient les valeurs des nœuds pour lesquels une relation ordinale est définie (comme des valeurs numériques ou des caractères avec des séquences définies). 　 [Voir ici] pour l'arborescence (https://qiita.com/tagtagtag/items/c5c460633e1ac864937a).

Chaque nœud a 0, 1 et 2 nœuds enfants, et celui avec une valeur plus petite est défini comme un nœud enfant gauche et celui avec une valeur plus grande est défini comme un nœud enfant droit.

Dans la mesure où j'ai enquêté, je n'ai pas pu confirmer la définition exacte des nœuds avec la même valeur, je vais donc les inclure dans le bon nœud enfant dans cet article.

Veuillez noter qu'il existe une méthode pour supprimer les doublons dans certains cas.

Propriétés de l'arborescence de recherche de bisection

En raison de la définition ci-dessus, les valeurs plus petites que le nœud de sommet sont stockées dans la branche gauche, et les valeurs plus grandes que le nœud de sommet sont stockées dans la branche droite. Cette structure est conservée quelle que soit la position de l'arbre de dichotomie.

De plus, l'extrémité gauche de l'arborescence a la valeur minimale de l'ensemble et l'extrémité droite a la valeur maximale.

De plus, lorsque la valeur du nœud est sortie par traversée d'inodeur, l'ensemble est trié par ordre croissant et sorti.

Voir l'arbre de recherche de bisection du wiki

Pour éviter tout malentendu, 13 dans ce chiffre n'est pas à la bonne extrémité. L'extrémité droite est 14. 13 n'est pas un nœud enfant droit car il s'agit d'un enfant gauche de 14 nœuds.

la mise en oeuvre

Une classe Node a été définie pour implémenter la structure de données de l'arbre de dichotomie.

La classe Node a les valeurs de «self.data» et l'enfant de gauche «self.left» enfant de droite «self.right» comme valeurs du nœud. Les enfants gauche et droit par défaut sont «Aucun».

Une classe BST a été définie pour l'implémentation de l'arbre de dichotomie.

Dans le constructeur, j'ai défini «self.root» et défini la valeur par défaut sur «Aucun». De plus, self.insert (val) est exécuté pour ajouter un nouveau nœud. L'introduction de la méthode est illustrée ci-dessous.

Implémenté ce qui suit comme méthode Voir le code pour plus de détails.

Ajouter un nœud
Vérifier la présence d'un nœud avec une certaine valeur
Obtenez la valeur minimale
Obtenez le maximum
Valeur de sortie avec inoder

J'ai trouvé les points suivants intéressants dans cette structure de données.

Le but de l'arbre de dichotomie est de partir de l'itinéraire et de le diviser à gauche et à droite en fonction de la valeur.
Si une note est stockée à la destination, elle ira plus loin à partir de ce point.
Lorsque vous atteignez la fin, ajoutez-le ici.
Le miso est trié par ordre du haut.


class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


class BST:
    def __init__(self, arr):
        self.root = None

        for val in arr:
            self.insert(val)
    
    def insert(self, val):
        if self.root is None:
            self.root = Node(val)

        else:
            node = self.root
            flag = True

            while flag:
                if node.data > val:
                    if node.left is None:
                        node.left = Node(val)
                        flag = False 
                        #Définissez False pour terminer pendant
                    else:
                        node = node.left
                else:
                    if node.right is None:
                        node.right = Node(val)
                        flag = False
                    else:
                        node = node.right


    def find(self, node, val):
        if node is not None:
            if node.data == val:
                return True

            else:
                flag_left = self.find(node.left, val) 
                flag_right = self.find(node.right, val)
            
                if flag_left or flag_right:
                    return True

        return False

    def bst_min(self, node):
        if node.left is None:
            return node.data
        else:
           return self.bst_min(node.left) 
           #Si vous souhaitez renvoyer la valeur atteinte par récursive, écrivez une fonction récursive après retour. Veuillez noter que l'utilisation est différente de celle de la traversée.
        
    def bst_max(self, node):
        if node.right is None:
            return node.data
        else:
            return self.bst_max(node.right)

    def inoder_traverse(self, node):
        if node is not None:
            self.inoder_traverse(node.left)
            print(node.data)
            self.inoder_traverse(node.right)

Courir

Exécuté comme suit

import random

arr = [random.randint(1, 100) for _ in range(12)]
ins = BST(arr)
print('insert node list =>', arr)
print('Is there No.4 ->', ins.find(ins.root, 4))
print('root', ins.root.data)
print('min', ins.bst_min(ins.root))
print('max', ins.bst_max(ins.root))
print('--------------------------')
print('Trié lors de la sortie dans l'ordre de passage')
ins.inoder_traverse(ins.root)

résultat

La liste qui est insérée change à chaque fois, donc si vous l'essayez plusieurs fois, vous obtiendrez une meilleure compréhension.

insert node list => [48, 10, 21, 58, 61, 12, 5, 87, 35, 2, 7, 39]
Is there No.4 -> False
root 48
min 2
max 87
--------------------------
Trié lors de la sortie dans l'ordre de passage
2
5
7
10
12
21
35
39
48
58
61
87

Les références

Introduction à la structure des données et à l'algorithme (O'Reilly)
[Explication de la bifurcation par Wikipedia](https://ja.wikipedia.org/wiki/%E6%9C%A8%E6%A7%8B%E9%80%A0_(%E3%83%87%E3) % 83% BC% E3% 82% BF% E6% A7% 8B% E9% 80% A0))