cracking-the-coding-interview-python/BSTreeNode.py at master · aihex/cracking-the-coding-interview-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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
from TreeNode import TreeNode
import random


class BSTreeNode(TreeNode):
    @staticmethod
    def create_from_array(array):
        if not all([array[i] <= array[i+1] for i in xrange(len(array) - 1)]):
            array = sorted(array)
        return BSTreeNode.create_from_array_rec(array, 0, len(array)-1)

    @staticmethod
    def create_from_array_rec(array, start, end):
        if start > end:
            return None
        mid = (start + end) >> 1
        node = BSTreeNode(array[mid])
        node.left = BSTreeNode.create_from_array_rec(array, start, mid-1)
        node.right = BSTreeNode.create_from_array_rec(array, mid+1, end)
        if node.left:
            node.left.parent = node
        if node.right:
            node.right.parent = node
        return node

    def insert(self, val):
        if val < self.val:
            if self.left:
                self.left.insert(val)
            else:
                self.left = BSTreeNode(val)
                if self.left:
                    self.left.parent = self
        else:
            if self.right:
                self.right.insert(val)
            else:
                self.right = BSTreeNode(val)
                if self.right:
                    self.right.parent = self

    # def delete(self, val):
    #     node = self.find(val)
    #     if not node:
    #         return self
    #     if node.left and node.right:
    #         tmp = node.right
    #         while tmp.left:
    #             tmp = tmp.left
    #         node.val = tmp.val
    #         return tmp.replace(self, tmp.right)
    #     elif node.left:
    #         return node.replace(self, node.left)
    #     elif node.right:
    #         return node.replace(self, node.right)
    #     else:
    #         return node.replace(self)
    #
    # def replace(self, root, node=None):
    #     if self == root:
    #         if node:
    #             node.parent = None
    #         return node
    #     else:
    #         if self.parent.left == self:
    #             self.parent.left = node
    #         else:
    #             self.parent.right = node
    #         if node:
    #             node.parent = self.parent
    #         return root

    def delete(self, val):
        node = self.find(val)
        if not node:
            return self
        if node.left:
            cur = node.left
            while cur.right:
                cur = cur.right
            node.val = cur.val
            if cur.parent.left == cur:
                cur.parent.left = cur.left
                if cur.left:
                    cur.left.parent = cur.parent
            else:
                cur.parent.right = cur.left
                if cur.left:
                    cur.left.parent = cur.parent
            cur.parent = None
            return self
        elif node.right:
            cur = node.right
            while cur.left:
                cur = cur.left
            node.val = cur.val
            if cur.parent.left == cur:
                cur.parent.left = cur.right
                if cur.right:
                    cur.right.parent = cur.parent
            else:
                cur.parent.right = cur.right
                if cur.right:
                    cur.right.parent = cur.parent
            cur.parent = None
            return self
        else:
            if node.parent:
                if node.parent.left == node:
                    node.parent.left = None
                else:
                    node.parent.right = None
                node.parent = None
                return self

    def find(self, val):
        if self.val == val:
            return self
        elif self.val < val:
            if self.right:
                return self.right.find(val)
        else:
            if self.left:
                return self.left.find(val)

if __name__ == '__main__':
    array = [random.randint(0, 10000) for i in xrange(100)]
    # array = [1, 1, 42]
    print array
    # root1 = BSTreeNode.create_from_array(array)
    # root1.inorder_print()
    print
    root2 = BSTreeNode(array[0])
    for i in xrange(1, len(array)):
        root2.insert(array[i])
    root2.inorder_print()
    print '-----',
    root2.preorder_print()
    print
    for i in array[:]:
        print 'delete ' + str(i)
        root2 = root2.delete(i)
        if root2:
            root2.inorder_print()
            print '-----',
            root2.preorder_print()
            print