[PYTHON] Un arbre de recherche de 2 minutes est un parent de la chaîne de hachage!?
Bonsoir (* ´ω ｀)
En amateur, À première vue, qu'est-ce qu'un «arbre»? .. (Désolé pour tous les experts m (_ _) m)
La structure arborescente semble être une structure de données qui exprime la relation hiérarchique entre les données.
Personnellement, cela ressemblait à une extension de la chaîne Hash précédente. J'étais enthousiasmé par le genre de pensée que c'était Pour le moment, je vais jouer avec (rires)
test.py
class Node:
def __init__(self,key,value,left:None,right:None):
self.key = key
self.value = value
self.left = left
self.right = right
C'est peut-être comme ça, mais j'ai écrit le contenu du nœud.
De cette manière, plus de nœuds peuvent être stockés dans les zones gauche et droite à l'intérieur du nœud.
J'ai essayé de le rendre un peu plus boisé.
C'est similaire à la chaîne Hash, c'est intéressant.
Je suis sûr qu'il existe des règles sur la façon de stocker les données. Oui, il y avait des règles. ..
Un arbre bifurqué est un arbre bifurqué dans lequel ** tous les nœuds ** remplissent les conditions suivantes. La clé de nœud du sous-arbre de gauche est ** plus petite ** que cette clé de nœud La clé de nœud du sous-arbre droit est ** plus grande ** que cette clé de nœud
Le sous-arbre gauche est l'enfant gauche, le sous-arbre droit est le bon noko, enfant!? (Rires)
De qui juger à droite ou à gauche, il semble qu'il n'y a pas de problème si vous pensez au tournant.
Comment c'est? Où que vous soyez, les conditions ci-dessus sont remplies! ??
Mais pourquoi avez-vous une telle règle? (11) La raison en est la règle de réglage des clés fournie précédemment. Essayez de trouver clé = 5.
- Le point de départ commence à 11, qui est appelé la racine. La clé que je recherchais était 5. Les clés plus petites que l'emplacement actuel (= 11) ont été stockées sur le côté gauche.
- Ouvrons le pointeur gauche. Il y avait dans ce nœud, clé = 5 !!
C'est un objectif heureux.
Cherchons maintenant une autre clé = 9.
La transition est colorée en rouge.
- commencez à partir de 11 (racine), touche (= 9) <11, alors allez à gauche !!
- key (= 9) est supérieur à 5, alors allez à droite !!
- clé (= 9) est plus grande que 7, alors allez à droite !! Il y avait la clé = 9 !!, Allez ---- Le !!
Je vois, en concevant le prochain pointeur fourni dans la chaîne Hash Encore plus concis, il réalise logiquement des structures de données complexes. génial!!
test.py
class Node:
def __init__(self,key,value,left:None,right:None):
self.key = key
self.value = value
self.left = left
self.right = right
class BinarySearchTree:
def __init__(self):
self.root = None
def search(self,key):
#commencer à partir de la racine!!
p = self.root
while True:
#return None si la structure n'a rien de connecté à root
if p.key is None:
return None
#Si la clé est applicable, p.valeur de retour
if p.key == key:
return p.value
#Tout d'abord, p mentionné ci-dessus.key ==Puisque la clé est passée,
#Décrivez la transition vers la droite ou la gauche ci-dessous
elif p.key < key:
p = p.right
else:
p = p.left
Pour le moment, décrivez le nœud de base et Ajout de la description à rechercher. À ce stade, Tree n'a rien fait. Maintenant, il n'y a qu'une racine vide. Ajoutons un nœud ici.
Tout d'abord, créons à partir de la racine.
test.py
def add(self,key,value):
#Au début, il était défini dans Node comme suit.
#class BinarySearchTree:
# def __init__(self):
# self.root = None
if self.root is None:
#Les données correspondantes peuvent également être stockées en root.
#left ,Je vais faire tout de suite, donc je vais laisser comme Aucun pour le moment
self.root = Node(key,value,None,None)
else:
#Si Node est déjà inséré dans root
#Vous devez commencer à partir de la racine et ajouter plus de nœuds.
#Comme vous vous en doutez, ajoutez_Nous allons configurer le nœud de manière récursive.
BinarySearchTree.add_node(self.root,key,value)
Une fois que vous avez créé la racine Sur la base de la racine, nous ajouterons des nœuds selon la définition de la dichotomie ci-dessus. Ce qui suit est une description de add_node qui se branche de manière récursive.
test.py
def add_node(node,key,value):
#Échec si une clé en double est trouvée
if key == node.key:
return print("fail to add")
#Nouveau nœud.key <Nœud existant.Si clé, stocker à gauche!
elif key < node.key:
#Si le pointeur gauche est vide, ajoutez-le en tant que nouveau nœud
if node.left is None:
node.left = Node(key,value,None,None)
#S'il y a déjà un magasin à gauche, traitez-le de manière récursive
else:
BinarySearchTree.add_node(node.left,key,value)
else:
#Si le pointeur droit est vide, ajoutez-le en tant que nouveau nœud
if node.right is None:
node.right = Node(key,value,None,None)
#Si right a déjà un magasin, traitez-le de manière récursive
else:
BinarySearchTree.add_node(node.right,key,value)
return True
Chaque fois que vous exécutez add, démarrez à partir de la racine, recherchez le pointeur correspondant et ajoutez Node. C'est comme si la plante, nourrie par la racine, suivait sa propre définition de la croissance. C'est juste un "arbre" qui pousse petit à petit. Je veux voir une créature palpitante.
Faire une telle image en lisant et en écrivant le code de texte Êtes-vous en train de vous sourire? !! (* ´з`) Cela signifie que vous ressentez votre propre croissance (rires).
Ensuite, il faut supprimer. Comme mentionné précédemment, Add commence par root et Je prends des mesures pour trouver la pièce pertinente et ajouter des nœuds à tout moment. Par conséquent, supprimer est le même, Accédez à la racine pour trouver le nœud que vous souhaitez supprimer.
C'est un peu compliqué. C'est peut-être trop difficile à penser, Dans ce cas, plongez-vous. m (_ _) m
Allons-y. Comme mentionné ci-dessus, tout commence par root. C'est fini si tu as ce que tu veux en tant que root Si root n'a pas de clé en premier lieu, c'est fini, non? ??
test.py
def remove(self,key):
#Commencez à partir de la racine avec le pointeur comme p.
p = self.root
#Qu'il vienne de la droite ou de la gauche, c'est un drapeau utile plus tard.
direction_is_left = None
while True:
#Si root ou Node n'a pas de clé, retournez False et quittez
if p.key is None:
print("root has no Node or tree has no Node that you want,faile")
return False
#Si la clé contenue dans le nœud correspond à la clé d'entrée, sortez en
if p.key == key:
print("find out the Node")
break
#Si la touche ne correspond pas à Node, sélectionnez le sens de déplacement vers la droite ou vers la gauche selon la règle ci-dessus.
#À ce moment, donnez une valeur au drapeau dans le sens du déplacement.(direction_is_left)
else:
if p.key > key:
direction_is_left = True
p = p.left
else:
direction_is_left = False
p = p.right
Comme le montre la figure ci-dessous, si le nœud à supprimer n'a pas d'enfants et s'il n'en a qu'un,
Comment le supprimer? ??
Dans ce cas, il ne semble y avoir aucun moyen de faire quoi que ce soit à moins de toucher le parent .gauche ou .droite un niveau supérieur.
Par conséquent, ajoutez un "parent" à la description ci-dessus pour faciliter la recherche du nœud supprimé et identifier également son parent.
test.py
def remove(self,key):
p = self.root
parent = None #Ciel(Kara)Préparez les parents
direction_is_left = None
while True:
if p.key is None:
print("root has no Node or tree has no Node that you want,faile")
return False
if p.key == key:
print("find out the Node")
break
else:
#Peu importe que vous alliez à droite ou à gauche, définissez la valeur de p sur p.left or p.droit et
#Attribuez p comme parent avant la mise à jour.
parent = p
if p.key > key:
direction_is_left = True
p = p.left
else:
direction_is_left = False
p = p.right
Je le posterai à nouveau!
Si vous n'avez aucun ou un enfant, vous vous concentrez sur la partie gauche ou droite.
test.py
#Il n'y a pas de droite, oui, ça se réfère au cas de la partie gauche
if p.right is None:
#Du point de vue des parents, p venait de la gauche, non?
if direction_is_left:
#Dans le cas de la figure ci-dessus, à gauche, Aucun est stocké à gauche du nœud de 1.
#Dans la figure ci-dessus, dans le cas de la droite, le nœud 1 est possible pour la gauche du nœud de 4
parent.left = p.left
else:
#??↓ Qu'est-ce que c'est? ('Д').. Je suis désolé, comme indiqué ci-dessous.
parent.right = p.left
Mais il y a des moments où vous souhaitez supprimer root, par exemple, non?
Dans la description ci-dessus, il n'y a pas de nœud sur le côté droit, donc
Vous devez remplacer le nœud de gauche pour le rendre root, non?
Donc, si vous souhaitez supprimer root, ajoutez-le également.
test.py
if p.right is None:
if p == self.root: #Je veux supprimer la racine??
self.root = p.left #Créons maintenant la racine du nœud gauche.
if direction_is_left:
parent.left = p.left
else:
parent.right = p.left
Si tel est le cas sans le droit, C'est pareil même s'il n'y a pas de gauche, non? C'est pourquoi je vais également lister la version sans la gauche.
test.py
if p.left is None:
if p == self.root:
self.root = p.right
if direction_is_left:
parent.left = p.right
else:
parent.right = p.right
elif p.right is None:
if p == self.root:
self.root = p.left
if direction_is_left:
parent.left = p.left
else:
parent.right = p.left
Donc, c'est la partie la plus difficile,
Que faire si vous souhaitez supprimer un nœud qui a deux enfants?
Vous souhaitez supprimer 5 comme indiqué ci-dessus.
Certes, il y avait une telle règle, non?
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ Un arbre bifurqué est un arbre bifurqué dans lequel ** tous les nœuds ** remplissent les conditions suivantes. La clé de nœud du sous-arbre de gauche est ** plus petite ** que cette clé de nœud La clé de nœud du sous-arbre droit est ** plus grande ** que cette clé de nœud ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
En d'autres termes, extrayez la valeur maximale de l'enfant sur la partie gauche, Si vous pouvez le remplacer, vous pouvez vous connecter avec l'enfant de droite, non?
C'est vrai, si vous avez deux enfants Avec l'idée ci-dessus, trouvez la valeur maximale, Remplacez le nœud que vous souhaitez supprimer. En post-traitement, la valeur maximale trouvée est supprimée. Déposons-le dans le code comme indiqué, 4 est le maximum.
test.py
else:
#Vous pouvez utiliser les informations dans 5 plus tard.
#Laissons ça comme parent
parent = p
#Laissez le nœud à gauche du parent être laissé
left = p.left
#Vrai parce que la direction du voyage est vers la gauche
direction_is_left = True
#Comme le montre la figure ci-dessus, 4 nœuds correspondant à 5 à gauche sont
#C'est la valeur maximale parmi les enfants de la partie gauche.
#Réécrivons les informations du nœud 5 en nœud 4.
p.key = left.key
p.value = left.value
#Supprimons Node 4.
#Plus précisément, parent.de gauche à gauche.Remplacer 1 pour gauche!!Tel quel(Lol)
if direction_is_left:
parent.left = left.left
#↓ Quoi???cette??
else:
parent.right = left.left
Finalement, il y eut une mystérieuse description.
Une mise à jour qui a été fermée paisiblement,
Et si la configuration de l'arborescence était comme ça?
Lors du branchement de gauche à droite
La valeur du droit augmente régulièrement.
Nous devons donc ajouter un moyen de trouver la valeur maximale.
test.py
else:
parent = p
left = p.left
direction_is_left = True
#Ajout de la bonne recherche!!
#left.Mettre à jour de gauche à droite devient Aucun
while left.right is None:
#Si vous trouvez le nœud sur la droite, mettez à jour le parent et la gauche
parent = left
left = left.right
#Déclarez que vous venez de la droite avec Faux
direction_is_left = False
p.key = left.key
p.value = left.value
if direction_is_left:
parent.left = left.left
#Si vous souhaitez définir le nœud trouvé à partir de la droite comme valeur maximale,
#left.laissé aux parents.Connectez-vous à droite.
else:
parent.right = left.left
C'est pourquoi remove est devenu un gros volume.
test.py
def remove(self,key):
p = self.root
parent = None
direction_is_left = None
while True:
if p.key is None:
print("root has no Node or tree has no Node that you want,faile")
return False
if p.key == key:
print("find out the Node")
break
else:
parent = p
if p.key > key:
direction_is_left = True
p = p.left
else:
direction_is_left = False
p = p.right
if p.left is None:
if p == self.root:
self.root = p.right
if direction_is_left:
parent.left = p.right
else:
parent.right = p.right
elif p.right is None:
if p == self.root:
self.root = p.left
if direction_is_left:
parent.left = p.left
else:
parent.right = p.left
else:
parent = p
left = p.left
direction_is_left = True
while left.right is None:
parent = left
left = left.right
direction_is_left = False
p.key = left.key
p.value = left.value
if direction_is_left:
parent.left = left.left
else:
parent.right = left.left
return True
Si vous pouvez imaginer ce que vous voulez faire avec supprimer Je pense que vous pouvez le lire d'une manière ou d'une autre. Merci pour votre travail acharné (´ ー ｀) y- ~~
Recommended Posts