Dalam tutorial ini, anda akan belajar bagaimana Binary Search Tree berfungsi. Anda juga akan dapati contoh kerja Binary Search Tree di C, C ++, Java dan Python.
Pohon carian binari adalah struktur data yang dengan cepat membolehkan kita mengekalkan senarai nombor yang disusun.
- Ia dipanggil pokok binari kerana setiap simpul pokok mempunyai maksimum dua anak.
- Ia disebut sebagai pohon carian kerana dapat digunakan untuk mencari kehadiran nombor dalam
O(log(n))waktu.
Sifat yang memisahkan pokok carian binari dari pokok binari biasa adalah
- Semua nod subtree kiri kurang daripada nod akar
- Semua nod subtree kanan lebih banyak daripada simpul akar
- Kedua-dua subtore setiap nod juga BST iaitu mempunyai dua sifat di atas
Pokok yang mempunyai subtree kanan dengan satu nilai lebih kecil daripada akar ditunjukkan untuk menunjukkan bahawa itu bukan pohon carian binari yang sah
Pokok binari di sebelah kanan bukan pokok carian binari kerana subtree kanan nod "3" mengandungi nilai yang lebih kecil darinya.
Terdapat dua operasi asas yang boleh anda lakukan pada pokok carian binari:
Operasi Carian
Algoritma bergantung pada sifat BST bahawa jika setiap subtree kiri mempunyai nilai di bawah root dan setiap subtree kanan mempunyai nilai di atas root.
Sekiranya nilainya berada di bawah akar, kita dapat mengatakan dengan pasti bahawa nilainya tidak berada di subtree yang betul; kita hanya perlu mencari di subtree kiri dan jika nilainya berada di atas root, kita dapat mengatakan dengan pasti bahawa nilainya tidak ada di subtree kiri; kita hanya perlu mencari di subtree yang betul.
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 cuba menggambarkannya dengan gambarajah.
4 tidak dijumpai begitu, melintasi subtree kiri 8 
4 tidak dijumpai begitu, melintasi subtree kanan 3 
4 tidak dijumpai begitu, melintasi subtree kiri 6 4 dijumpai
Sekiranya nilainya dijumpai, kami mengembalikan nilainya sehingga dapat disebarkan dalam setiap langkah rekursi seperti yang ditunjukkan pada gambar di bawah.
Sekiranya anda perasan, kami telah memanggil carian kembali (nod simpul *) empat kali. Apabila kita mengembalikan sama ada nod baru atau NULL, nilainya dikembalikan berulang kali sehingga carian (root) mengembalikan hasil akhir.
Sekiranya nilainya dijumpai di salah satu subtitre, nilainya disebarkan sehingga pada akhirnya dikembalikan, jika tidak, nol dikembalikan
Sekiranya nilainya tidak dijumpai, akhirnya kita mencapai anak kiri atau kanan simpul daun yang NULL dan ia akan disebarkan dan dikembalikan.
Masukkan Operasi
Memasukkan nilai pada kedudukan yang betul mirip dengan pencarian kerana kita berusaha mengekalkan peraturan bahawa subtree kiri lebih rendah daripada root dan subtree kanan lebih besar daripada root.
Kami terus menuju ke subtree kanan atau subtree kiri bergantung pada nilainya dan apabila kita mencapai titik subtree kiri atau kanan tidak ada, kita meletakkan simpul 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;
Algoritma tidak semudah yang kelihatan. Mari cuba gambarkan bagaimana kita menambah nombor 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 
Masukkan 4 sebagai anak kiri 6
Kami telah memasang simpul tetapi kami masih harus keluar dari fungsi tersebut tanpa melakukan kerosakan pada bahagian pokok yang lain. Di sinilah return node;akhirnya berguna. Dalam kes NULL, simpul yang baru dibuat dikembalikan dan dilampirkan ke nod induk, jika tidak, simpul yang sama dikembalikan tanpa perubahan ketika kita naik sehingga kita kembali ke akar.
Ini memastikan bahawa semasa kita bergerak kembali ke atas pokok, sambungan simpul yang lain tidak berubah.
Imej yang menunjukkan pentingnya mengembalikan elemen akar pada akhir supaya elemen tidak kehilangan kedudukannya semasa langkah rekursi ke atas.
Operasi Penghapusan
Terdapat tiga kes untuk menghapus nod dari pokok carian binari.
Kes I
Dalam kes pertama, simpul yang akan dihapuskan adalah simpul daun. Sekiranya demikian, hapus simpul dari pokok.
4 akan dipadam 
Padam nod
Kes II
Dalam kes kedua, simpul yang akan dihapuskan mempunyai nod anak tunggal. Sekiranya demikian, ikuti langkah-langkah di bawah:
- Gantikan nod itu dengan nod turunannya.
- Tanggalkan simpul anak dari kedudukan asalnya.
6 akan dihapus 
salin nilai anaknya ke nod dan hapus anak 
Akhir anak
Kes III
Dalam kes ketiga, simpul yang akan dihapus mempunyai dua anak. Sekiranya demikian, ikuti langkah-langkah di bawah:
- Dapatkan pengganti urutan simpul itu.
- Gantikan nod dengan pengganti inorder.
- Keluarkan pengganti penyusun dari kedudukan asalnya.
3 akan dihapus Salin nilai penerus inorder (4) ke nod 
Hapus pengganti inorder
Contoh Python, Java dan C / C ++
Python Java C 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); )
Kerumitan Pokok Carian Binari
Kerumitan Masa
| Operasi | Kerumitan Kes Terbaik | Kerumitan Kes Purata | Kerumitan Kes Terburuk |
| Cari | O (log n) | O (log n) | O (n) |
| Penyisipan | O (log n) | O (log n) | O (n) |
| Penghapusan | O (log n) | O (log n) | O (n) |
Di sini, n adalah bilangan nod di pokok.
Kerumitan Ruang
Kerumitan ruang untuk semua operasi adalah O (n).
Aplikasi Pohon Carian Binari
- Dalam pengindeksan bertingkat di pangkalan data
- Untuk menyusun dinamik
- Untuk menguruskan kawasan memori maya di kernel Unix
