Lunski's Clutter

This is a place to put my clutters, no matter you like it or not, welcome here.

0%

Binary Search Tree

Posted on Edited on In
Symbols count in article: 6.9k Reading time ≈ 6 mins.

樹狀結構

背景知識

OO, python基礎語法

理解問題

設計樹狀結構，包含插入，刪除，中序尋訪與取得最小值。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
 Let us create following BST
              50
           /      \
          30      70
         /  \    /  \
       20  40   60   80 
       
中序MLR: 20 30 40 50 60 70 80

TC:  O(hight), search:O(logn) 
SC:  O(n)

class BST { 
    class Node { 
        int key; 
        Node left, right; 
   
        public Node(int data){ 
            key = data; 
            left = right = null; 
        } 
    } 
    Node root; 
  
    BST(){ 
        root = null; 
    } 

    // insert a node in BST 
    void insert(int key)  { 
        root = insert_Recursive(root, key); 
    } 
   
    //recursive insert function
    Node insert_Recursive(Node root, int key) { 
          //tree is empty
        if (root == null) { 
            root = new Node(key); 
            return root; 
        } 
        //traverse the tree
        if (key < root.key)     //insert in the left subtree
            root.left = insert_Recursive(root.left, key); 
        else if (key > root.key)    //insert in the right subtree
            root.right = insert_Recursive(root.right, key); 
          // return pointer
        return root; 
    } 
    
    //delete a node from BST
    void deleteKey(int key) { 
        root = delete_Recursive(root, key); 
    } 
   
    //recursive delete function
    Node delete_Recursive(Node root, int key)  { 
        //tree is empty
        if (root == null)  return root; 
   
        //traverse the tree
        if (key < root.key)     //traverse left subtree 
            root.left = delete_Recursive(root.left, key); 
        else if (key > root.key)  //traverse right subtree
            root.right = delete_Recursive(root.right, key); 
        else  { 
            // node contains only one child
            if (root.left == null) 
                return root.right; 
            else if (root.right == null) 
                return root.left; 
   
            // node has two children; 
            //get inorder successor (min value in the right subtree) 
            root.key = minValue(root.right); 
   
            // Delete the inorder successor 
            root.right = delete_Recursive(root.right, root.key); 
        } 
        return root; 
    } 
    
    // min value is left most
    int minValue(Node root)  { 
        //initially
        int minval = root.key; 
        
        //find minval
        while (root.left != null)  { 
            minval = root.left.key; 
            root = root.left; 
        } 
        return minval; 
    } 

    // method for inorder traversal of BST 
    void inorder() { 
        inorder_Recursive(root); 
    } 
   
    // recursively traverse the BST  
    void inorder_Recursive(Node root) { 
        if (root != null) { 
            inorder_Recursive(root.left); 
            System.out.print(root.key + " "); 
            inorder_Recursive(root.right); 
        } 
    } 
     
    boolean search(int key)  { 
        root = search_Recursive(root, key); 
        if (root!= null)
            return true;
        else
            return false;
    } 
   
    //recursive insert function
    Node search_Recursive(Node root, int key)  { 
        // Base Cases: root is null or key is present at root 
        if (root==null || root.key==key) 
            return root; 
        // val is greater than root's key 
        if (root.key > key) 
            return search_Recursive(root.left, key); 
        // val is less than root's key 
        return search_Recursive(root.right, key); 
    } 
}
class Main{
    public static void main(String[] args)  { 
        BST bst = new BST(); 
        /* BST tree example
              50
           /      \
          30      70
         /  \    /  \
       20   40  60   80   */
        //insert data into BST
        bst.insert(50); 
        bst.insert(30); 
        bst.insert(20); 
        bst.insert(40); 
        bst.insert(70); 
        bst.insert(60); 
        bst.insert(80); 
        bst.inorder(); 
        
        //delete leaf node  
        System.out.println("\n Delete leaf 20:"); 
        bst.deleteKey(20); 
        bst.inorder(); 
        
        //delete the node with one child
        System.out.println("\n Delete 1 child 40:"); 
        bst.deleteKey(40); 
        bst.inorder(); 
                 
        //delete node with two children  
        System.out.println("\n Delete 2 children 70:"); 
        bst.deleteKey(70); 
        bst.inorder(); 
        
        System.out.println();
        
        //search a key in the BST
        boolean ret_val = bst.search (50);
        System.out.println("\nKey 50 found in BST:" + ret_val );
        ret_val = bst.search (20);
        System.out.println("\nKey 20 found in BST:" + ret_val );
     } 
}

Python

  • 基礎結構
1
2
3
4
5
6
7
class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.val = data
        
class Tree:
  • 新增
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def insert(self, root , data):
  # 1. check root exist
  if root is None:
    return Node(data)
  else:
    # 2. root == data, return root
    if root.val == data:
      return root
    # 3. root < data, insert right
    elif root.val < data:
      root.right = self.insert(root.right, data)
    # 4. root > data, insert left
    else:
      root.left = self.insert(root.left, data)
  return root
  • 刪除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# to determine smallest node to delete
# travel to lefmostleaf
def minValueNode(self, node):
    while(node.left is not None):
        node = node.left
    return node

def delete(self, root, data):
  # 1. check root exist   
  if root is None: return root
  else:
    # 2. root < data, delete right
    if root.val < data:
      root.right = self.delete(root.right, data) 
    # 3. root > data, delete left
    elif root.val > data:
      root.left = self.delete(root.left, data)
    else: 
      # Node with one 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        
        
      # Node with two children:
      # Get the inorder successor
      # (smallest in the right subtree)
      temp = self.minValueNode(root.right)

      # Copy the inorder successor's
      # content to this node
      root.val = temp.val

      # Delete the inorder successor
      root.right = self.delete(root.right, temp.val)
 
    return root
  • 中序尋訪
1
2
3
4
5
def inorder(self, root):
    if root:
        self.inorder(root.left)
        print(root.val)
        self.inorder(root.right)

  • 搜尋

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def search(self, root, data):
        while True:        
            if root.val == data:
                return root.val
            elif root.val > data:
                if root.left:
                    root = root.left
                else:
                    raise Exception('node not found')
            elif root.val < data: 
                if root.right:
                    root = root.right
                else:
                    raise Exception('node not found')

  • main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
root = None
tree = Tree()
root = tree.insert(root, 50)
print(root)
tree.insert(root, 30)
tree.insert(root, 20)
tree.insert(root, 40)
tree.insert(root, 70)
tree.insert(root, 60)
tree.insert(root, 80)

print ("Inorder traversal of the given tree")
tree.inorder(root)

print ("\nDelete 20")
tree.delete(root, 20)
print ("Inorder traversal of the modified tree")
tree.inorder(root)

print ("\nDelete 30")
tree.delete(root, 30)
print ("Inorder traversal of the modified tree")
tree.inorder(root)
 
print ("\nDelete 70")
tree.delete(root, 70)
print ("Inorder traversal of the modified tree")
tree.inorder(root)
      
print ("\nSearch 70")
tree.search(root, 70)

>
Inorder traversal of the given tree
20
30
40
50
60
70
80
Delete 20
Inorder traversal of the modified tree
30
40
50
60
70
80

Delete 30
Inorder traversal of the modified tree
40
50
60
70
80

Delete 70
Inorder traversal of the modified tree
40
50
60
80

Search 70
Traceback (most recent call last):
  File "<string>", line 117, in <module>
  File "<string>", line 85, in search
Exception: node not found

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Welcome to my other publishing channels