Dalam tutorial ini, Anda akan mempelajari cara kerja Binary Search Tree. Juga, Anda akan menemukan contoh kerja Binary Search Tree di C, C ++, Java dan Python.
Pohon pencarian biner adalah struktur data yang dengan cepat memungkinkan kita untuk mempertahankan daftar angka yang diurutkan.
- Disebut pohon biner karena setiap simpul pohon memiliki maksimal dua anak.
- Ini disebut pohon pencarian karena dapat digunakan untuk mencari keberadaan angka dalam
O(log(n))waktu.
Properti yang memisahkan pohon pencarian biner dari pohon biner biasa adalah
- Semua simpul dari sub pohon kiri lebih kecil dari simpul akar
- Semua simpul dari sub pohon kanan lebih dari sekedar simpul akar
- Kedua subpohon dari setiap node juga BST yaitu mereka memiliki dua properti di atas
Pohon yang memiliki subpohon kanan dengan satu nilai lebih kecil dari akar ditampilkan untuk menunjukkan bahwa itu bukan pohon pencarian biner yang valid
Pohon biner di sebelah kanan bukanlah pohon pencarian biner karena subtree kanan dari node "3" berisi nilai yang lebih kecil darinya.
Ada dua operasi dasar yang dapat Anda lakukan di pohon pencarian biner:
Operasi Pencarian
Algoritme bergantung pada properti BST yang jika setiap subpohon kiri memiliki nilai di bawah akar dan setiap subpohon kanan memiliki nilai di atas akar.
Jika nilainya di bawah root, kita dapat mengatakan dengan pasti bahwa nilainya tidak berada di subtree yang benar; kita hanya perlu mencari di subtree kiri dan jika nilainya di atas root, kita bisa memastikan bahwa nilainya tidak ada di subtree kiri; kita hanya perlu mencari di subtree kanan.
Algoritma:
If root == NULL return NULL; If number == root->data return root->data; If number data return search(root->left) If number> root->data return search(root->right)
Mari kita coba memvisualisasikannya dengan diagram.
4 tidak ditemukan jadi, lintasan melalui subpohon kiri 8 
4 tidak ditemukan jadi, lintasan melalui subpohon kanan dari 3 
4 tidak ditemukan sehingga, melintasi subpohon kiri dari 6 4 ditemukan
Jika nilainya ditemukan, kami mengembalikan nilai tersebut sehingga disebarkan di setiap langkah rekursi seperti yang ditunjukkan pada gambar di bawah.
Jika Anda mungkin telah memperhatikan, kami telah memanggil pencarian kembali (node struktural *) empat kali. Ketika kita mengembalikan node baru atau NULL, nilainya akan dikembalikan lagi dan lagi sampai pencarian (root) mengembalikan hasil akhir.
Jika nilai ditemukan di salah satu subpohon, itu disebarkan sehingga pada akhirnya dikembalikan, jika tidak null dikembalikan
Jika nilainya tidak ditemukan, kami akhirnya mencapai anak kiri atau kanan dari node daun yang NULL dan disebarkan dan dikembalikan.
Sisipkan Operasi
Memasukkan nilai pada posisi yang benar mirip dengan pencarian karena kami mencoba mempertahankan aturan bahwa subtree kiri lebih kecil dari root dan subtree kanan lebih besar dari root.
Kami terus pergi ke subtree kanan atau subtree kiri tergantung pada nilainya dan ketika kami mencapai titik subtree kiri atau kanan adalah null, kami meletakkan node baru di sana.
Algoritma:
If node == NULL return createNode(data) if (data data) node->left = insert(node->left, data); else if (data> node->data) node->right = insert(node->right, data); return node;
Algoritmanya tidak sesederhana kelihatannya. Mari kita coba memvisualisasikan bagaimana kita menambahkan angka ke BST yang ada.
4 <8 jadi, melintang melalui anak kiri 8 
4> 3 jadi, melintang melalui anak kanan 8 
4 <6 jadi, melintang melalui anak kiri 6 
Sisipkan 4 sebagai anak kiri 6
Kami telah memasang simpul tetapi kami masih harus keluar dari fungsi tanpa melakukan kerusakan pada bagian pohon lainnya. Di sinilah return node;bagian akhir berguna. Dalam kasus NULL, node yang baru dibuat dikembalikan dan dilampirkan ke node induk, jika tidak node yang sama dikembalikan tanpa perubahan apa pun saat kita naik sampai kita kembali ke root.
Ini memastikan bahwa saat kita kembali ke atas pohon, koneksi node lainnya tidak berubah.
Gambar yang menunjukkan pentingnya mengembalikan elemen root di bagian akhir agar elemen tidak kehilangan posisinya selama langkah rekursi ke atas.
Operasi Penghapusan
Ada tiga kasus untuk menghapus node dari pohon pencarian biner.
Kasus I
Pada kasus pertama, simpul yang akan dihapus adalah simpul daun. Dalam kasus seperti itu, cukup hapus node dari pohon.
4 akan dihapus 
Hapus node
Kasus II
Dalam kasus kedua, simpul yang akan dihapus kebohongannya memiliki simpul anak tunggal. Dalam kasus seperti itu, ikuti langkah-langkah di bawah ini:
- Ganti node tersebut dengan node turunannya.
- Hapus simpul anak dari posisi aslinya.
6 harus dihapus 
salin nilai anaknya ke node dan hapus 
pohon Final anak
Kasus III
Dalam kasus ketiga, node yang akan dihapus memiliki dua anak. Dalam kasus seperti itu, ikuti langkah-langkah di bawah ini:
- Dapatkan penerus inorder dari node tersebut.
- Ganti node dengan penerus inorder.
- Hapus penerus inorder dari posisi aslinya.
3 harus dihapus Salin nilai penerus inorder (4) ke node 
Hapus penerus inorder
Contoh Python, Java dan C / C ++
Python Java C ++ # Binary Search Tree operations in Python # Create a node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Inorder traversal def inorder(root): if root is not None: # Traverse left inorder(root.left) # Traverse root print(str(root.key) + "->", end=' ') # Traverse right inorder(root.right) # Insert a node def insert(node, key): # Return a new node if the tree is empty if node is None: return Node(key) # Traverse to the right place and insert the node if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) return node # Find the inorder successor def minValueNode(node): current = node # Find the leftmost leaf while(current.left is not None): current = current.left return current # Deleting a node def deleteNode(root, key): # Return if the tree is empty if root is None: return root # Find the node to be deleted if key root.key): root.right = deleteNode(root.right, key) else: # If the node is with only one child or no child if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp # If the node has two children, # place the inorder successor in position of the node to be deleted temp = minValueNode(root.right) root.key = temp.key # Delete the inorder successor root.right = deleteNode(root.right, temp.key) return root root = None root = insert(root, 8) root = insert(root, 3) root = insert(root, 1) root = insert(root, 6) root = insert(root, 7) root = insert(root, 10) root = insert(root, 14) root = insert(root, 4) print("Inorder traversal: ", end=' ') inorder(root) print("Delete 10") root = deleteNode(root, 10) print("Inorder traversal: ", end=' ') inorder(root)
// Binary Search Tree operations in Java class BinarySearchTree ( class Node ( int key; Node left, right; public Node(int item) ( key = item; left = right = null; ) ) Node root; BinarySearchTree() ( root = null; ) void insert(int key) ( root = insertKey(root, key); ) // Insert key in the tree Node insertKey(Node root, int key) ( // Return a new node if the tree is empty if (root == null) ( root = new Node(key); return root; ) // Traverse to the right place and insert the node if (key root.key) root.right = insertKey(root.right, key); return root; ) void inorder() ( inorderRec(root); ) // Inorder Traversal void inorderRec(Node root) ( if (root != null) ( inorderRec(root.left); System.out.print(root.key + " -> "); inorderRec(root.right); ) ) void deleteKey(int key) ( root = deleteRec(root, key); ) Node deleteRec(Node root, int key) ( // Return if the tree is empty if (root == null) return root; // Find the node to be deleted if (key root.key) root.right = deleteRec(root.right, key); else ( // If the node is with only one child or no child if (root.left == null) return root.right; else if (root.right == null) return root.left; // If the node has two children // Place the inorder successor in position of the node to be deleted root.key = minValue(root.right); // Delete the inorder successor root.right = deleteRec(root.right, root.key); ) return root; ) // Find the inorder successor int minValue(Node root) ( int minv = root.key; while (root.left != null) ( minv = root.left.key; root = root.left; ) return minv; ) // Driver Program to test above functions public static void main(String() args) ( BinarySearchTree tree = new BinarySearchTree(); tree.insert(8); tree.insert(3); tree.insert(1); tree.insert(6); tree.insert(7); tree.insert(10); tree.insert(14); tree.insert(4); System.out.print("Inorder traversal: "); tree.inorder(); System.out.println("After deleting 10"); tree.deleteKey(10); System.out.print("Inorder traversal: "); tree.inorder(); ) )
// Binary Search Tree operations in C #include #include struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root printf("%d -> ", root->key); // Traverse right inorder(root->right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); printf("Inorder traversal: "); inorder(root); printf("After deleting 10"); root = deleteNode(root, 10); printf("Inorder traversal: "); inorder(root); )
// Binary Search Tree operations in C++ #include using namespace std; struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root cout right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); cout << "Inorder traversal: "; inorder(root); cout << "After deleting 10"; root = deleteNode(root, 10); cout << "Inorder traversal: "; inorder(root); )
Kompleksitas Pohon Pencarian Biner
Kompleksitas Waktu
| Operasi | Kompleksitas Kasus Terbaik | Kompleksitas Kasus Rata-rata | Kompleksitas Kasus Terburuk |
| Cari | O (log n) | O (log n) | Di) |
| Insersi | O (log n) | O (log n) | Di) |
| Penghapusan | O (log n) | O (log n) | Di) |
Di sini, n adalah jumlah node di pohon.
Kompleksitas Ruang
Kompleksitas ruang untuk semua operasi adalah O (n).
Aplikasi Pohon Pencarian Biner
- Dalam pengindeksan bertingkat di database
- Untuk penyortiran dinamis
- Untuk mengelola area memori virtual di kernel Unix
