Wie kann ich einen Binary Search Tree erstellen

Question

Wie erstelle ich einen Binary Search Tree in C? Ist das nicht einfach nur ein Binary Tree? Was kann man in einem BST suchen was man in einem normalen Binary Tree nicht kann?

Answer 1

Ein Binary Search Tree ist eine spezielle Art eines Binary Tree mit einer besonderen Eigenschaft. In einem BST sind die Werte der Knoten so angeordnet, dass für jeden Knoten gilt:      

• Alle Knoten im linken Teilbaum haben einen Wert, der kleiner oder gleich dem Wert des aktuellen Knotens ist.     
• Alle Knoten im rechten Teilbaum haben einen Wert, der größer ist als der Wert des aktuellen Knotens.

Das Konzept hat Anwendungen in verschiedenen wissenschaftlichen und technischen Bereichen. Es gibt verschiedene Arten der Suche in einem BST.

• Minimum und Maximum suchen: Du könntest Funktionen implementieren, um das kleinste und das größte Element im BST zu finden. Dies könnte nützlich sein, um beispielsweise den Bereich der Werte im Baum zu bestimmen.      
• Vorgänger und Nachfolger suchen: Du könntest Funktionen schreiben, um den Vorgänger (größter Wert kleiner als der gegebene Wert) oder den Nachfolger (kleinster Wert größer als der gegebene Wert) eines gegebenen Wertes im BST zu finden.      
• Kleiner als, Größer als suchen: Du könntest eine Funktion implementieren, die alle Elemente im BST zurückgibt, die kleiner oder größer als ein gegebener Wert sind. Dies könnte nützlich sein, um eine Liste von Elementen mit bestimmten Eigenschaften zu erhalten.      
• Bereichssuche: Du könntest eine Funktion schreiben, die alle Elemente im BST zurückgibt, die innerhalb eines bestimmten Wertebereichs liegen.      
• K-nearest-neighbor-Suche: Du könntest eine Funktion erstellen, um die K nächsten Nachbarn eines gegebenen Wertes im BST zu finden. Dies könnte in Anwendungen wie räumlicher Suche oder Empfehlungssystemen nützlich sein.

Hier ist ein Beispiel, wie du eine einfache Suche (ob ein bestimmtes Element enthalten ist) in einem BST durchführen könntest.

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

struct TreeNode* insert(struct TreeNode* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }

    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }

    return root;
}

struct TreeNode* search(struct TreeNode* root, int key) {
    if (root == NULL || root->data == key) {
        return root;
    }

    if (key < root->data) {
        return search(root->left, key);
    } else {
        return search(root->right, key);
    }
}

int main() {
    struct TreeNode* root = NULL;
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    root = insert(root, 3);
    root = insert(root, 7);

    int key = 7;
    struct TreeNode* result = search(root, key);
    if (result != NULL) {
        printf("Element %d gefunden!\n", key);
    } else {
        printf("Element %d nicht gefunden.\n", key);
    }

    return 0;
}