Pohon Biner dalam Struktur Data (CONTOH)
Sarah Chen
Apa itu Pohon Biner?
Kata biner berarti dua. Dalam struktur data pohon “Pohon Biner” berarti pohon yang setiap nodenya dapat memiliki maksimal dua node anak (node kiri dan kanan). Ini adalah pohon biner sederhana.
Namun, ada pohon biner lain yang paling sering digunakan dan memiliki beberapa kasus penggunaan. Pohon ini disebut Pohon Pencarian Biner (BST). Pohon ini dapat membuat algoritma pencarian jauh lebih cepat, tepatnya kompleksitas waktu log(n). Dalam struktur data, n berarti jumlah simpul dalam pohon biner.
Apa Perbedaan Antara Pohon Biner dan Pohon Pencarian Biner?
Perbedaan BST dengan Binary Tree biasa adalah pada BST node kiri mempunyai nilai lebih kecil dibandingkan node root, dan node kanan mempunyai nilai lebih besar dibandingkan node root. Jadi, subpohon kiri akan selalu berisi nilai yang lebih kecil dari akarnya, dan subpohon kanan akan selalu berisi nilai lebih besar dari akarnya.
Contoh Pohon Pencarian Biner
Mari kita ambil contoh berikut untuk menunjukkan konsep Pohon Pencarian Biner.
Di sini Anda dapat semua node mengikuti disiplin yang diberikan. Ada rumus untuk jumlah maksimum node di Pohon Pencarian Biner. Jika kita mengamati pohon di atas, kita dapat melihat setiap node memiliki dua anak kecuali semua node daun. Dan tinggi(h) Pohon Biner yang diberikan adalah 4. Rumusnya adalah 2h - 1. Jadi, hasilnya adalah 15.
Gambar di atas bukanlah Pohon Biner Lengkap atau Pohon Biner Seimbang, melainkan disebut Pohon Biner Lengkap atau Pohon Biner Seimbang. Ada Struktur Data lain yang disebut AVL (jenis lain dari Pohon Biner) yang mengoptimalkan ketinggian Pohon Biner dan melakukan pencarian BST lebih cepat seperti pada Gambar 3.
Cobalah untuk menghitung traversal berurutan dari Pohon Biner yang diberikan di atas. Anda akan menemukan bahwa ini akan memberikan array yang diurutkan tidak menurun, dan algoritma Traversal akan sama dengan Pohon Biner.
Jenis Pohon Biner
Berikut adalah beberapa jenis Pohon Biner yang penting:
- Pohon Biner Penuh: Setiap node dapat memiliki 0 atau 2 node anak di pohon biner ini. Hanya satu simpul anak yang tidak diperbolehkan dalam jenis pohon biner ini. Jadi, kecuali node daun, semua node akan memiliki 2 anak.
- Pohon Biner Penuh: Setiap node dapat memiliki 0 atau 2 node. Kelihatannya seperti Pohon Biner Penuh, namun semua elemen daunnya condong ke subpohon kiri, sedangkan pada pohon biner penuh simpulnya bisa berada di subpohon kanan atau kiri.
- Pohon Biner Sempurna: Semua simpul harus memiliki 0 atau 2 simpul, dan semua simpul daun harus berada pada tingkat atau tinggi yang sama. Contoh struktur pohon biner penuh di atas bukanlah Pohon Biner Sempurna karena simpul 6 dan simpul 1,2,3 tidak berada pada ketinggian yang sama. Namun contoh Pohon Biner Lengkap adalah pohon biner sempurna.
- Pohon Biner yang Merosot: Setiap node hanya dapat memiliki satu anak. Semua operasi seperti pencarian, penyisipan, dan penghapusan membutuhkan waktu O(N).
- Pohon Biner Seimbang: Di sini pohon biner ini, perbedaan tinggi subpohon kiri dan kanan paling banyak adalah 1. Jadi, saat menambah atau menghapus sebuah simpul, kita perlu menyeimbangkan kembali tinggi pohon tersebut. Jenis Pohon Biner Self-Balanced disebut Pohon AVL.
Ada tiga operasi dasar BST. Hal tersebut dibahas secara rinci di bawah ini.
Implementasi Pohon Biner di C dan C++
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int value;
struct Node *left, *right;
}
struct Node *getEmptynode(int val)
{
struct Node *tempNode = (struct Node *)malloc(sizeof(struct Node));
tempNode->value = val;
tempNode->left = NULL;
tempNode->right = NULL;
return tempNode;
}
struct Node *successor(struct Node *node)
{
struct Node *present = node;
// going to the left most node
while (present != NULL && present->left != NULL)
{
present = present->left;
}
return present;
}
struct Node *insert(struct Node *node, int value)
{
if (node == NULL)
{
return getEmptynode(value);
}
if (value < node->value)
{
node->left = insert(node->left, value);
}
else
{
node->right = insert(node->right, value);
}
return node;
}
int searchInBST(struct Node *node, int value)
{
struct Node *current = node;
while (current->value != value)
{
if (current->value > value)
{
current = current->left;
}
else
{
current = current->right;
}
if (current == NULL)
{
return 0;
}
}
return 1;
}
void inorder(struct Node *root)
{
if (root != NULL)
{
inorder(root->left);
cout << root->value << " ";
inorder(root->right);
}
}
struct Node *deleteNode(struct Node *node, int value)
{
if (node == NULL)
{
return node;
}
if (value < node->value)
{
node->left = deleteNode(node->left, value);
}
else if (value > node->value)
{
node->right = deleteNode(node->right, value);
}
else
{
if (node->left == NULL)
{
struct Node *temp = node->right;
free(node);
return temp;
}
else if (node->right == NULL)
{
struct Node *temp = node->left;
free(node);
return temp;
}
struct Node *temp = successor(node->right);
node->value = temp->value;
node->right = deleteNode(node->right, temp->value);
}
return node;
}
int main()
{
struct Node *root = NULL;
root = insert(root, 8);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 2);
root = insert(root, 6);
root = insert(root, 10);
root = insert(root, 14);
root = insert(root, 1);
root = insert(root, 3);
root = insert(root, 5);
root = insert(root, 7);
root = insert(root, 9);
root = insert(root, 11);
root = insert(root, 13);
root = insert(root, 15);
cout << "InOrder Traversal after inserting all nodes: " << endl;
inorder(root);
root = insert(root, -10);
cout << "\nInOrder Traversal after inserting -10 : " << endl;
inorder(root);
cout << "\nSearching -5 in the BST: " << searchInBST(root, -5) << endl;
cout << "Searching -10 in the BST: " << searchInBST(root, -10) << endl;
root = deleteNode(root,8);
cout<<"After deleting node 8, inorder traversal: "<<endl;
inorder(root);
root = deleteNode(root,-10);
cout<<"\nAfter deleting node -10, inorder traversal: "<<endl;
inorder(root);
}
Keluaran:
InOrder Traversal after inserting all nodes: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: 0 Searching -10 in the BST: 1 After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
Implementasi Pohon Biner di Python
class Node:
def __init__(self,value):
self.left = None
self.right = None
self.value = value
def insert(root,value):
if root == None:
return Node(value)
if value< root.value:
root.left = insert(root.left,value)
else:
root.right = insert(root.right,value)
return root
def searchInBST(root,value):
current = root
while current.value != value:
if current.value > value:
current = current.left
else:
current = current.right
if current == None:
return "Not found"
return "Found"
def inorder(root):
if root != None:
inorder(root.left)
print(root.value,end=" ")
inorder(root.right)
def successor(root):
present = root
while present != None and present.left != None:
present = present.left
return present
def deleteNode(root,value):
if root == None:
return root
if value < root.value:
root.left = deleteNode(root.left, value)
elif value>root.value:
root.right = deleteNode(root.right, value)
else:
if root.left == None:
temp = root.right
root = None
return temp
elif root.right == None:
temp = root.left
root = None
return temp
temp = successor(root.right)
root.value = temp.value
root.right = deleteNode(root.right, temp.value)
return root
root = Node(8)
root = insert(root, 4)
root = insert(root, 12)
root = insert(root, 2)
root = insert(root, 6)
root = insert(root, 10)
root = insert(root, 14)
root = insert(root, 1)
root = insert(root, 3)
root = insert(root, 5)
root = insert(root, 7)
root = insert(root, 9)
root = insert(root, 11)
root = insert(root, 13)
root = insert(root, 15)
print("InOrder Traversal after inserting all nodes: ")
inorder(root)
root = insert(root, -10)
print("\nInOrder Traversal after inserting -10 : ")
inorder(root)
print("\nSearching -5 in the BST: ",searchInBST(root, -5))
print("Searching -5 in the BST: ",searchInBST(root, -10))
root = deleteNode(root,8)
print("After deleting node 8, inorder traversal:")
inorder(root)
root = deleteNode(root,-10)
print("\nAfter deleting node -10, inorder traversal:")
inorder(root)
Keluaran:
InOrder Traversal after inserting all nodes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : -10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: Not found Searching -5 in the BST: Found After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
Penerapan Pohon Biner
Berikut adalah beberapa aplikasi umum dari Pohon Biner:
- Mengatur data node dalam urutan yang diurutkan
- Digunakan di peta dan mengatur objek node di perpustakaan bahasa pemrograman.
- Mencari elemen dalam struktur data
» Pelajari tutorial kami berikutnya tentang Algoritma Kombinasi
