algorithm-practice-python/binary_search_tree.py at main · anzmin/algorithm-practice-python · GitHub

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
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.parent = None

class BST():
    def __init__(self, root): # self는 instance를 나타내는 듯?
        self.root = root

    def search(self, value):
        node = self.root

        while node:
            temp = node
            if node.value == value:
                return node
            elif node.value > value:
                node = node.left
                node.parent = temp
            else:
                node = node.right
                node.parent = temp

        return False

    def insert(self, value):
        node = self.root
        while True:
            if value < node.value:
                if node.left != None:
                    node = node.left
                else:
                    node.left = Node(value)
                    break
            else:
                if node.right != None:
                    node = node.right
                else:
                    node.right = Node(value)
                    break

    def delete(self, value):

        node = self.search(value)
        if node == False:
            return False
        parent = node.parent

        # non-chile
        if node.left == None and node.right == None:
            if value < parent.value:
                parent.left = None
            else:
                parent.right = None

        # one left child
        if node.left != None and node.right == None:
            if value < parent.value:
                parent.left = node.left
            else:
                parent.right = node.left

        # one right child
        if node.left == None and node.right != None:
            if value < parent.value:
                parent.left = node.right
            else:
                parent.right = node.right

        # two child
        if node.left != None and node.right != None:
            new = node.right
            new_parent = node.right
            while new.left != None:
                new_parent = new
                new = new.left # find successor

            if new.right != None:
                new_parent.left = new.right
            else:
                new_parent.left = None

            if value < parent.value:
                parent.left = new # node delete and connect to new node
                new.left = node.left # copy left
                new.right = node.right # copy right
            else:
                parent.right = new
                new.left = node.left
                new.right = node.right

        return True

    def parent_value(self, value):
        temp = bst.search(value)
        if temp.parent != None: print(temp.parent.value)
        else: print(None)
        return

    def left_value(self, value):
        temp = bst.search(value)
        if temp.left != None: print(temp.left.value)
        else: print(None)
        return

    def right_value(self, value):
        temp = bst.search(value)
        if temp.right != None: print(temp.right.value)
        else: print(None)
        return


if __name__ == "__main__":

    root = Node(1)
    bst = BST(root) # root를 node(1)로 선언
    bst.insert(4)
    bst.insert(5)
    bst.insert(7)
    bst.insert(3)
    bst.parent_value(3)
    bst.delete(4)
    bst.parent_value(3)
    bst.left_value(3)