[PYTHON] [Introduction] J'ai essayé de l'implémenter moi-même tout en expliquant l'arbre de dichotomie
[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))