Binary Search Tree

 

    Binary tree adalah struktur data non linier bentuk khusus dari pohon umum (general tree) yang diilhami dari pohon yang kita lihat sehari-hari. Namun, karena ini merupakan pohon imajiner maka bentuknya bisa dibolak-balik sesuai yang kita inginkan.

    Pohon umum di gambar 1 memiliki 7 simpul (7 nodes), yaitu A, B, C, D, E, F, dan G. Setiap simpul bisa memiliki hubungan dengan 0, 1, 2, 3, atau berapapun simpul lain. Yang dikatakan hubungan adalah garis yang menghubungkan simpul tersebut dengan simpul-simpul di bawahnya. Karena ketidakpastian banyaknya simpul yang dapat berhubungan dengan simpul lain, maka akan menimbulkan kesulitan jika akan dilakukan komputerisasinya. Kalau masing-masing dipatok (default) dengan penyediaan sebanyak 5 hubungan dari masing-masing simpul, maka, jika akhirnya hanya digunakan 1 sampai 3 saja, berakibat terjadinya pemborosan penggunaan memori. Sebaliknya, jika hanya disediakan 3 hubungan dari setiap simpul tetapi pada akhirnya banyak yang memiliki hubungan dengan lebih dari 3 simpul lain, maka akan terjadi loosing data.

Operasi dalam binary tree : 

• insert(data)
• inOrderTraverse()
• preOrderTraverse()
• postOrderTraverse()
• search(data)
• remove(data)

DATA HOSTED WITH ♥ BY PASTEBIN.COM - DOWNLOAD RAW - SEE ORIGINAL

1. class BST_class {
2.      class Node {
3.        int key;
4.        Node left, right;
5.  
6.        public Node(int data){
7.          key = data;
8.          left = right = null;
9.      }
10. }
11. Node root;
12.  
13. BST_class(){
14.        root = null;
15. }
16. void deleteKey(int key) {
17.        root = delete_Recursive(root, key);
18. }
19.  
20. Node delete_Recursive(Node root, int key) {
21.        if (root == null) return root;
22.        if (key < root.key)
23.          root.left = delete_Recursive(root.left, key);
24.        else if (key > root.key)
25.          root.right = delete_Recursive(root.right, key);
26.        else{
27.          if (root.left == null)
28.              return root.right;
29.          else if (root.right == null)
30.              return root.left;
31.          root.key = minValue(root.right);
32.          root.right = delete_Recursive(root.right, root.key);
33.      }
34.      return root;
35. }
36.  
37. int minValue(Node root) {
38.      int minval = root.key;
39.      while (root.left != null) {
40.        minval = root.left.key;
41.        root = root.left;
42.      }
43.      return minval;
44. }
45. void insert(int key) {
46.      root = insert_Recursive(root, key);
47. }
48. Node insert_Recursive(Node root, int key) {
49.      if (root == null) {
50.        root = new Node(key);
51.        return root;
52.      }
53.      if (key < root.key)
54.        root.left = insert_Recursive(root.left, key);
55.      else if (key > root.key)
56.        root.right = insert_Recursive(root.right, key);
57.      return root;
58. }
59.  
60. void inorder() {
61.      inorder_Recursive(root);
62. }
63.  
64. void inorder_Recursive(Node root) {
65.      if (root != null) {
66.        inorder_Recursive(root.left);
67.        System.out.print(root.key + " ");
68.        inorder_Recursive(root.right);
69.     }
70. }
71.  
72. boolean search(int key) {
73.      root = search_Recursive(root, key);
74.      if (root!= null)
75.        return true;
76.      else
77.        return false;
78. }
79.  
80. Node search_Recursive(Node root, int key) {
81.      if (root==null || root.key==key)
82.        return root;
83.      if (root.key > key)
84.        return search_Recursive(root.left, key);
85.      return search_Recursive(root.right, key);
86.    }
87. }
88. class Main{
89.      public static void main(String[] args) {
90.        BST_class bst = new BST_class();
91.  
92.        bst.insert(20);
93.        bst.insert(10);
94.        bst.insert(5);
95.        bst.insert(40);
96.        bst.insert(90);
97.        bst.insert(50);
98.        System.out.println("The BST Created with input data(Left-root-right):");
99.        bst.inorder();
100.  
101.        System.out.println("\\nThe BST after Delete 20(leaf node):");
102.        bst.deleteKey(20);
103.        bst.inorder();
104.        System.out.println("\\nThe BST after Delete 90 (node with 1 child):");
105.        bst.deleteKey(90);
106.        bst.inorder();
107.        System.out.println("\\nThe BST after Delete 40 (Node with two children):");
108.        bst.deleteKey(40);
109.        bst.inorder();
110.        boolean ret_val = bst.search (50);
111.        System.out.println("\\nKey 50 found in BST:" + ret_val );
112.        ret_val = bst.search (20);
113.        System.out.println("\\nKey 20 found in BST:" + ret_val );
114.     }
115. }