Binary Search Tree

Binary Search Tree merupakan struktur data pohon biner dengan menggunakan node. BST mempunyai ciri-ciri sebagai berikut :

•           Subtree sebelah kiri hanya berisi node yang memiliki key yang lebih kecil dari node itu sendiri
•           Subtree sebelah kanan hanya berisi node yang memiliki key yang lebih besar dari node itu sendiri
•           Subtree kiri kanan juga berupa BST
•           Tidak boleh ada node yang sama atau duplikat

Cara Searching key dalam Binary Search Tree adalah mencocokan key yang kita cari dengan key dalam root, jika key sesuai dengan root maka kita return root, jika key lebih kecil dari key dalam root, maka kita pindahkan pencarian ke subtree sebelah kiri, dan jika key lebih besar dari key dalam root, maka kita pindahkan pencarian ke subtree sebelah kanan.

Contoh dalam C :

struct node

{

    int key;

    struct node *left, *right;

};

   

struct node *newNode(int item)

{

    struct node *temp =  (struct node *)malloc(sizeof(struct node));

    temp->key = item;

    temp->left = temp->right = NULL;

    return temp;

}

   

void inorder(struct node *root)

{

    if (root != NULL)

    {

        inorder(root->left);

        printf("%d \n", root->key);

        inorder(root->right);

    }

}

   

struct node* insert(struct node* node, int key)

{

    if (node == NULL) return newNode(key);

  

    if (key < node->key)

        node->left  = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);   

    return node;

}

   

int main()

{

    struct node *root = NULL;

    root = insert(root, 50);

    insert(root, 30);

    insert(root, 20);

    insert(root, 40);

    insert(root, 70);

    insert(root, 60);

    insert(root, 80);

   

    inorder(root);

   

    return 0;

}

Output :

20

30

40

50

60

70

80

Worst Case Time Complexity dari BST adalah O(n) dimana key yang kita cari ada di leaf paling bawah sehingga n adalah tinggi dari tree tersebut.