Datenstruktur des binären Suchbaums anhand von Beispielen erläutert

Ein Baum ist eine Datenstruktur aus Knoten mit den folgenden Merkmalen:

  1. Jeder Baum hat einen Wurzelknoten (oben) mit einem bestimmten Wert.
  2. Der Wurzelknoten hat null oder mehr untergeordnete Knoten.
  3. Jeder untergeordnete Knoten hat null oder mehr untergeordnete Knoten usw. Dadurch wird ein Teilbaum im Baum erstellt. Jeder Knoten hat einen eigenen Teilbaum, der aus seinen Kindern und ihren Kindern usw. besteht. Dies bedeutet, dass jeder Knoten für sich ein Baum sein kann.

Ein binärer Suchbaum (BST) fügt diese beiden Merkmale hinzu:

  1. Jeder Knoten hat maximal zwei untergeordnete Knoten.
  2. Für jeden Knoten sind die Werte seiner linken absteigenden Knoten kleiner als die des aktuellen Knotens, was wiederum kleiner ist als die der rechten absteigenden Knoten (falls vorhanden).

Das BST basiert auf der Idee des binären Suchalgorithmus, der ein schnelles Nachschlagen, Einfügen und Entfernen von Knoten ermöglicht. Die Art und Weise, wie sie eingerichtet sind, bedeutet, dass die Operationen im Durchschnitt bei jedem Vergleich etwa die Hälfte des Baums überspringen können, sodass jede Suche, Einfügung oder Löschung Zeit benötigt, die proportional zum Logarithmus der Anzahl der im Baum gespeicherten Elemente ist. O(log n).

Manchmal kann jedoch der schlimmste Fall eintreten, wenn der Baum nicht ausgeglichen ist und die Zeitkomplexität O(n)für alle drei dieser Funktionen gilt. Aus diesem Grund sind selbstausgleichende Bäume (AVL, Rot-Schwarz usw.) viel effektiver als die Basis-BST.

Beispiel für ein Worst-Case-Szenario: Dies kann passieren, wenn Sie immer wieder Knoten hinzufügen, die immer größer als der vorherige Knoten (dessen übergeordneter Knoten) sind. Dasselbe kann passieren, wenn Sie immer Knoten mit Werten hinzufügen, die niedriger als ihre übergeordneten Knoten sind.

Grundlegende Operationen auf einer BST

  • Erstellen: Erstellt einen leeren Baum.
  • Einfügen: Fügen Sie einen Knoten in den Baum ein.
  • Suchen: Sucht nach einem Knoten im Baum.
  • Löschen: Löscht einen Knoten aus dem Baum.

Erstellen

Zunächst wird ein leerer Baum ohne Knoten erstellt. Die Variable / Kennung, die auf den Wurzelknoten zeigen muss, wird mit einem NULLWert initialisiert .

Suche

Sie beginnen immer mit der Suche im Baum am Wurzelknoten und gehen von dort aus nach unten. Sie vergleichen die Daten in jedem Knoten mit denen, die Sie suchen. Wenn der verglichene Knoten nicht übereinstimmt, fahren Sie entweder mit dem rechten oder dem linken Kind fort. Dies hängt vom Ergebnis des folgenden Vergleichs ab: Wenn der gesuchte Knoten niedriger ist als der, mit dem Sie ihn verglichen haben, Sie gehen zum linken Kind, andernfalls (wenn es größer ist) gehen Sie zum rechten Kind. Warum? Da die BST (gemäß ihrer Definition) strukturiert ist, ist das rechte Kind immer größer als das Elternteil und das linke Kind immer kleiner.

Einfügen

Es ist der Suchfunktion sehr ähnlich. Sie beginnen erneut an der Wurzel des Baums und gehen rekursiv nach unten, um nach der richtigen Stelle zum Einfügen unseres neuen Knotens zu suchen, wie in der Suchfunktion erläutert. Wenn sich bereits ein Knoten mit demselben Wert im Baum befindet, können Sie entweder das Duplikat einfügen oder nicht. Einige Bäume erlauben Duplikate, andere nicht. Dies hängt von der jeweiligen Implementierung ab.

Löschen

Es gibt 3 Fälle, die auftreten können, wenn Sie versuchen, einen Knoten zu löschen. Wenn ja,

  1. Kein Teilbaum (keine Kinder): Dieser ist der einfachste. Sie können den Knoten einfach löschen, ohne dass zusätzliche Aktionen erforderlich sind.
  2. Ein Teilbaum (ein untergeordnetes Element): Sie müssen sicherstellen, dass das untergeordnete Element nach dem Löschen des Knotens mit dem übergeordneten Knoten des gelöschten Knotens verbunden ist.
  3. Zwei Teilbäume (zwei untergeordnete Bäume): Sie müssen den zu löschenden Knoten suchen und durch seinen Nachfolger ersetzen (den am weitesten entfernten Knoten im rechten Teilbaum).

Die zeitliche Komplexität zum Erstellen eines Baums beträgt O(1). Die zeitliche Komplexität für das Suchen, Einfügen oder Löschen eines Knotens hängt von der Höhe des Baums ab h. Der schlimmste Fall ist also O(h).

Vorgänger eines Knotens

Vorgänger können als der Knoten beschrieben werden, der direkt vor dem Knoten kommt, an dem Sie sich gerade befinden. Um den Vorgänger des aktuellen Knotens zu finden, sehen Sie sich den am weitesten rechts liegenden / größten Blattknoten im linken Teilbaum an.

Nachfolger eines Knotens

Nachfolger können als der Knoten beschrieben werden, der direkt nach dem Knoten kommt, an dem Sie sich gerade befinden. Um den Nachfolger des aktuellen Knotens zu finden, sehen Sie sich den am weitesten links stehenden / kleinsten Blattknoten im rechten Teilbaum an.

Spezielle Arten von BT

  • Haufen
  • Rot-schwarzer Baum
  • B-Baum
  • Splay-Baum
  • N-ary Baum
  • Trie (Radixbaum)

Laufzeit

Datenstruktur: Array

  • Worst-Case-Leistung: O(log n)
  • Best-Case-Leistung: O(1)
  • Durchschnittliche Leistung: O(log n)
  • Worst-Case-Raumkomplexität: O(1)

Wo nist die Anzahl der Knoten in der BST.

Implementierung von BST

Hier ist eine Definition für einen BST-Knoten mit einigen Daten, die auf seinen linken und rechten untergeordneten Knoten verweisen.

struct node { int data; struct node *leftChild; struct node *rightChild; };

Suchvorgang

Wenn ein Element durchsucht werden soll, starten Sie die Suche vom Stammknoten aus. Wenn die Daten kleiner als der Schlüsselwert sind, suchen Sie im linken Teilbaum nach dem Element. Suchen Sie andernfalls nach dem Element im rechten Teilbaum. Befolgen Sie für jeden Knoten den gleichen Algorithmus.

struct node* search(int data){ struct node *current = root; printf("Visiting elements: "); while(current->data != data){ if(current != NULL) { printf("%d ",current->data); //go to left tree if(current->data > data){ current = current->leftChild; }//else go to right tree else { current = current->rightChild; } //not found if(current == NULL){ return NULL; } } } return current; }

Operation einfügen

Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

void insert(int data) { struct node *tempNode = (struct node*) malloc(sizeof(struct node)); struct node *current; struct node *parent; tempNode->data = data; tempNode->leftChild = NULL; tempNode->rightChild = NULL; //if tree is empty if(root == NULL) { root = tempNode; } else { current = root; parent = NULL; while(1) { parent = current; //go to left of the tree if(data data) { current = current->leftChild; //insert to the left if(current == NULL) { parent->leftChild = tempNode; return; } }//go to right of the tree else { current = current->rightChild; //insert to the right if(current == NULL) { parent->rightChild = tempNode; return; } } } } } 

Binary search trees (BSTs) also give us quick access to predecessors and successors. Predecessors can be described as the node that would come right before the node you are currently at.

  • To find the predecessor of the current node, look at the rightmost/largest leaf node in the left subtree. Successors can be described as the node that would come right after the node you are currently at.
  • To find the successor of the current node, look at the leftmost/smallest leaf node in the right subtree.

Let’s look at a couple of procedures operating on trees.

Since trees are recursively defined, it’s very common to write routines that operate on trees that are themselves recursive.

So for instance, if we want to calculate the height of a tree, that is the height of a root node, We can go ahead and recursively do that, going through the tree. So we can say:

  • For instance, if we have a nil tree, then its height is a 0.
  • Otherwise, We’re 1 plus the maximum of the left child tree and the right child tree.

So if we look at a leaf for example, that height would be 1 because the height of the left child is nil, is 0, and the height of the nil right child is also 0. So the max of that is 0, then 1 plus 0.

Height(tree) algorithm

if tree = nil: return 0 return 1 + Max(Height(tree.left),Height(tree.right))

Here is the code in C++

int maxDepth(struct node* node) { if (node==NULL) return 0; else { int rDepth = maxDepth(node->right); int lDepth = maxDepth(node->left); if (lDepth > rDepth) { return(lDepth+1); } else { return(rDepth+1); } } } 

We could also look at calculating the size of a tree that is the number of nodes.

  • Again, if we have a nil tree, we have zero nodes.

Otherwise, we have the number of nodes in the left child plus 1 for ourselves plus the number of nodes in the right child. So 1 plus the size of the left tree plus the size of the right tree.

Size(tree) algorithm

if tree = nil return 0 return 1 + Size(tree.left) + Size(tree.right)

Here is the code in C++

int treeSize(struct node* node) { if (node==NULL) return 0; else return 1+(treeSize(node->left) + treeSize(node->right)); }

Relevant videos on freeCodeCamp YouTube channel

  • Binary Search Tree
  • Binary Search Tree: Traversal and Height

Following are common types of Binary Trees:

Full Binary Tree/Strict Binary Tree: A Binary Tree is full or strict if every node has exactly 0 or 2 children.

 18 / \ 15 30 / \ / \ 40 50 100 40

In Full Binary Tree, number of leaf nodes is equal to number of internal nodes plus one.

Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

 18 / \ 15 30 / \ / \ 40 50 100 40 / \ / 8 7 9