algorithm
Binäre Suchbäume
Suche…
Einführung
Der binäre Baum ist ein Baum, bei dem jeder Knoten maximal zwei Kinder hat. Binary Search Tree (BST) ist ein binärer Baum, dessen Elemente in einer speziellen Reihenfolge angeordnet sind. In jeder BST sind alle Werte (dh Schlüssel) im linken Teilbaum niedriger als die Werte im rechten Teilbaum.
Binärer Suchbaum - Einfügung (Python)
Dies ist eine einfache Implementierung der binären Suchbaum-Einfügung mit Python.
Ein Beispiel ist unten gezeigt:
Nach dem Code-Snippet zeigt jedes Bild die Ausführungsvisualisierung, wodurch die Funktionsweise dieses Codes vereinfacht wird.
class Node:
def __init__(self, val):
self.l_child = None
self.r_child = None
self.data = val
def insert(root, node):
if root is None:
root = node
else:
if root.data > node.data:
if root.l_child is None:
root.l_child = node
else:
insert(root.l_child, node)
else:
if root.r_child is None:
root.r_child = node
else:
insert(root.r_child, node)
def in_order_print(root):
if not root:
return
in_order_print(root.l_child)
print root.data
in_order_print(root.r_child)
def pre_order_print(root):
if not root:
return
print root.data
pre_order_print(root.l_child)
pre_order_print(root.r_child)
Binärer Suchbaum - Löschen (C ++)
Bevor ich mit dem Löschen beginne, möchte ich nur ein wenig Licht auf einen binären Suchbaum (BST) setzen. Jeder Knoten in einem BST kann maximal zwei Knoten (linkes und rechtes untergeordnetes Element) haben Schlüssel kleiner oder gleich dem Schlüssel des übergeordneten Knotens. Der rechte Teilbaum eines Knotens hat einen größeren Schlüssel als der Schlüssel des übergeordneten Knotens.
Löschen eines Knotens in einer Baumstruktur unter Beibehaltung der binären Suchbaumeigenschaft.
Beim Löschen eines Knotens sind drei Fälle zu berücksichtigen.
- Fall 1: Der zu löschende Knoten ist der Blattknoten (Knoten mit Wert 22).
- Fall 2: Der zu löschende Knoten hat ein Kind (Knoten mit Wert 26).
- Fall 3: Der zu löschende Knoten hat beide Kinder (Knoten mit dem Wert 49).
Erklärung der Fälle:
- Wenn der zu löschende Knoten ein Blattknoten ist, löschen Sie einfach den Knoten und übergeben Sie
nullptran seinen übergeordneten Knoten. - Wenn ein zu löschender Knoten nur ein untergeordnetes Element enthält, kopieren Sie den untergeordneten Wert in den Knotenwert und löschen Sie das untergeordnete Element (In Fall 1 konvertiert).
- Wenn ein zu löschender Knoten über zwei untergeordnete Elemente verfügt, kann das Minimum aus dem rechten Teilbaum in den Knoten kopiert werden. Anschließend kann der Mindestwert aus dem rechten Teilbaum des Knotens gelöscht werden (in Fall 2 konvertiert).
Hinweis: Das Minimum im rechten Teilbaum kann maximal ein Kind und das zu rechte Kind enthalten, wenn das linke Kind vorhanden ist. Dies bedeutet, dass es nicht der Mindestwert ist oder der BST-Eigenschaft nicht folgt.
Die Struktur eines Knotens in einer Baumstruktur und der Code zum Löschen:
struct node
{
int data;
node *left, *right;
};
node* delete_node(node *root, int data)
{
if(root == nullptr) return root;
else if(data < root->data) root->left = delete_node(root->left, data);
else if(data > root->data) root->right = delete_node(root->right, data);
else
{
if(root->left == nullptr && root->right == nullptr) // Case 1
{
free(root);
root = nullptr;
}
else if(root->left == nullptr) // Case 2
{
node* temp = root;
root= root->right;
free(temp);
}
else if(root->right == nullptr) // Case 2
{
node* temp = root;
root = root->left;
free(temp);
}
else // Case 3
{
node* temp = root->right;
while(temp->left != nullptr) temp = temp->left;
root->data = temp->data;
root->right = delete_node(root->right, temp->data);
}
}
return root;
}
Die zeitliche Komplexität des obigen Codes ist O ( h ), wobei h die Höhe des Baums ist.
Niedrigster gemeinsamer Vorfahre in einer BST
Betrachten Sie die BST:
Der niedrigste gemeinsame Vorfahr von 22 und 26 ist 24
Der niedrigste gemeinsame Vorfahre von 26 und 49 ist 46
Der niedrigste gemeinsame Vorfahre von 22 und 24 ist 24
Die binäre Suchbaumeigenschaft kann verwendet werden, um den untersten Vorfahren der Knoten zu finden
Pseudo-Code:
lowestCommonAncestor(root,node1, node2){
if(root == NULL)
return NULL;
else if(node1->data == root->data || node2->data== root->data)
return root;
else if((node1->data <= root->data && node2->data > root->data)
|| (node2->data <= root->data && node1->data > root->data)){
return root;
}
else if(root->data > max(node1->data,node2->data)){
return lowestCommonAncestor(root->left, node1, node2);
}
else {
return lowestCommonAncestor(root->right, node1, node2);
}
}
Binärer Suchbaum - Python
class Node(object):
def __init__(self, val):
self.l_child = None
self.r_child = None
self.val = val
class BinarySearchTree(object):
def insert(self, root, node):
if root is None:
return node
if root.val < node.val:
root.r_child = self.insert(root.r_child, node)
else:
root.l_child = self.insert(root.l_child, node)
return root
def in_order_place(self, root):
if not root:
return None
else:
self.in_order_place(root.l_child)
print root.val
self.in_order_place(root.r_child)
def pre_order_place(self, root):
if not root:
return None
else:
print root.val
self.pre_order_place(root.l_child)
self.pre_order_place(root.r_child)
def post_order_place(self, root):
if not root:
return None
else:
self.post_order_place(root.l_child)
self.post_order_place(root.r_child)
print root.val
"" "Einen anderen Knoten erstellen und Daten einfügen" "" "
r = Node(3)
node = BinarySearchTree()
nodeList = [1, 8, 5, 12, 14, 6, 15, 7, 16, 8]
for nd in nodeList:
node.insert(r, Node(nd))
print "------In order ---------"
print (node.in_order_place(r))
print "------Pre order ---------"
print (node.pre_order_place(r))
print "------Post order ---------"
print (node.post_order_place(r))