[PYTHON] [Einführung] Ich habe versucht, es selbst zu implementieren, während ich den Dichotomiebaum erklärte
[Einführung] Ich habe versucht, es selbst zu implementieren, während ich den Dichotomiebaum erklärte
Zweck
- Ich möchte mein Verständnis von Datenstrukturen und Algorithmen vertiefen, indem ich den Dichotomiebaum lerne.
- Implementieren Sie einen Dichotomiebaum und eine Datenstruktur in Python.
- Es ist möglicherweise einfacher zu implementieren, wenn die Datenstruktur in eine eindimensionale Liste gefaltet ist. Um jedoch das Verständnis der Baumdatenstruktur zu vertiefen, wagen wir es, eine Knotenklasse zu definieren und einen Dichotomiebaum zu implementieren.
Inhalt
Definition des dichotomisierten Baumes
Ein Dichotomiebaum ist eine Dichotomiedatenstruktur, die die Werte von Knoten enthält, für die eine Ordnungsbeziehung definiert ist (z. B. numerische Werte oder Zeichen mit definierten Sequenzen). [Siehe hier] für die Baumstruktur (https://qiita.com/tagtagtag/items/c5c460633e1ac864937a).
Jeder Knoten hat 0, 1 und 2 untergeordnete Knoten, und der mit einem kleineren Wert wird als linker untergeordneter Knoten und der mit einem größeren Wert als rechter untergeordneter Knoten definiert.
Soweit ich untersucht habe, konnte ich die genaue Definition von Knoten mit demselben Wert nicht bestätigen, daher werde ich sie in den richtigen untergeordneten Knoten in diesem Artikel aufnehmen.
Bitte beachten Sie, dass es in einigen Fällen eine Methode zum Entfernen von Duplikaten gibt.
Eigenschaften des Bisektionssuchbaums
Aufgrund der obigen Definition werden Werte, die kleiner als der Scheitelpunktknoten sind, im linken Zweig und Werte, die größer als der Scheitelpunktknoten sind, im rechten Zweig gespeichert. Diese Struktur bleibt unabhängig von der Position des Dichotomiebaums erhalten.
Außerdem hat das linke Ende des Baums den Minimalwert der Menge und das rechte Ende den Maximalwert.
Wenn der Wert des Knotens durch Inoder-Traversal ausgegeben wird, wird die Menge in aufsteigender Reihenfolge sortiert und ausgegeben.
Siehe Wiki Bisection Search Tree
- Um Missverständnisse zu vermeiden, befindet sich 13 in dieser Abbildung nicht am richtigen Ende. Das rechte Ende ist 14. 13 ist kein rechter untergeordneter Knoten, da es ein linkes Kind von 14 Knoten ist.
Implementierung
Eine Knotenklasse wurde definiert, um die Datenstruktur des Dichotomiebaums zu implementieren.
Die Node-Klasse hat die Werte "self.data" und das linke Kind "self.left", das rechte Kind "self.right" als Werte des Knotens. Die standardmäßigen linken und rechten untergeordneten Elemente sind "Keine".
Für die Implementierung des Dichotomiebaums wurde eine BST-Klasse definiert.
Im Konstruktor habe ich "self.root" definiert und den Standardwert auf "None" gesetzt. Außerdem wird "self.insert (val)" ausgeführt, um einen neuen Knoten hinzuzufügen. Die Einführung der Methode ist unten dargestellt.
Folgendes wurde als Methode implementiert Einzelheiten finden Sie im Code.
- Fügen Sie einen Knoten hinzu
- Überprüfen Sie, ob ein Knoten mit einem bestimmten Wert vorhanden ist
- Holen Sie sich den Mindestwert
- Holen Sie sich maximal
- Ausgabewert mit Inoder
Ich fand die folgenden Punkte in dieser Datenstruktur interessant.
- Der Punkt des Dichotomiebaums besteht darin, von der Route aus zu beginnen und sie nach dem Wert nach links und rechts zu teilen.
- Wenn eine Notiz am Ziel gespeichert ist, wird sie von diesem Punkt aus tiefer gehen.
- Wenn Sie das Ende erreicht haben, fügen Sie es dort hinzu.
- Miso wird in der Reihenfolge von oben sortiert.
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
#Setzen Sie False, um während zu beenden
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)
#Wenn Sie den Wert zurückgeben möchten, der durch rekursiv erreicht wurde, schreiben Sie nach der Rückgabe eine rekursive Funktion. Bitte beachten Sie, dass sich die Verwendung von der von Traversal unterscheidet.
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)
Lauf
Wird wie folgt ausgeführt
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('Sortiert bei Ausgabe in der Reihenfolge der Übergabe')
ins.inoder_traverse(ins.root)
Ergebnis
Die Liste, die eingefügt wird, ändert sich jedes Mal. Wenn Sie es also einige Male versuchen, erhalten Sie ein besseres Verständnis.
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
--------------------------
Sortiert bei Ausgabe in der Reihenfolge der Übergabe
2
5
7
10
12
21
35
39
48
58
61
87
Verweise
- Einführung Datenstruktur und Algorithmus (O'Reilly)
- [Erklärung der Dichotomie durch 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))