Struktur Data - Pohon Pencarian Biner
A Binary Search Tree (BST) adalah pohon di mana semua node mengikuti properti yang disebutkan di bawah ini -
Nilai kunci sub-pohon kiri kurang dari nilai kunci simpul induknya (root).
Nilai kunci sub-pohon kanan lebih besar dari atau sama dengan nilai kunci simpul induknya (root).
Jadi, BST membagi semua sub-pohonnya menjadi dua segmen; sub-pohon kiri dan sub-pohon kanan dan dapat didefinisikan sebagai -
left_subtree (keys) < node (key) ≤ right_subtree (keys)
Perwakilan
BST adalah kumpulan node yang diatur sedemikian rupa sehingga mereka mempertahankan properti BST. Setiap node memiliki kunci dan nilai terkait. Saat mencari, kunci yang diinginkan dibandingkan dengan kunci di BST dan jika ditemukan, nilai terkait diambil.
Berikut adalah representasi bergambar BST -
Kami mengamati bahwa kunci simpul akar (27) memiliki semua kunci yang nilainya lebih rendah di sub-pohon kiri dan kunci bernilai lebih tinggi di sub-pohon kanan.
Operasi Dasar
Berikut adalah operasi dasar dari sebuah pohon -
Search - Mencari elemen di pohon.
Insert - Menyisipkan elemen di pohon.
Pre-order Traversal - Melintasi pohon dengan cara pre-order.
In-order Traversal - Melintasi pohon secara berurutan.
Post-order Traversal - Melintasi pohon dengan cara pasca-order.
Node
Tentukan node yang memiliki beberapa data, referensi ke node anak kiri dan kanannya.
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
Operasi Pencarian
Kapanpun sebuah elemen akan dicari, mulailah mencari dari root node. Kemudian jika datanya kurang dari nilai kunci, cari elemen di subtree kiri. Jika tidak, cari elemen di subtree kanan. Ikuti algoritma yang sama untuk setiap node.
Algoritma
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;
}
Sisipkan Operasi
Kapanpun sebuah elemen akan dimasukkan, pertama cari lokasi yang tepat. Mulailah mencari dari root node, kemudian jika datanya kurang dari nilai kunci, cari lokasi kosong di subtree kiri dan masukkan datanya. Jika tidak, cari lokasi kosong di subtree kanan dan masukkan datanya.
Algoritma
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 < parent->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;
}
}
}
}
}