structures-/Binary_Tree.py at master · BiaHawk/structures- · 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
148
class Node:

    def _init_(self, key, parent=None, left=None, right=None):
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right

    def _bool_(self):
        if self.key != None:
            return True
        return False


class Tree:

    def _init_(self, root):
        self.root = root

    def search(self, k):
        node = self.root
        while node and node.key != k:
            if k < node.key:
                node = node.left
            else:
                node = node.right
        if not node:
            print('Node with key \"{}\" not found.'.format(k))
        return node

    def maximum(self):
        node = self.root
        while node.right != None:
            node = node.right
        return node

    def minimum(self):
        node = self.root
        while node.left != None:
            node = node.left
        return node

    def insert(self, new_node):
        node = self.root
        if node == None:
            self.root = new_node
        else:
            k = new_node.key
            while True:
                if k <= node.key:
                    if node.left:
                        node = node.left
                    else:
                        node.left = new_node
                        new_node.parent = node
                        break
                else:
                    if node.right:
                        node = node.right
                    else:
                        node.right = new_node
                        new_node.parent = node
                        break

    def delete(self, k):
        node = self.search(k)
        if not node.left and not node.right:
            if k < node.parent.key:
                node.parent.left = None
            else:
                node.parent.right = None
        elif not node.left:
            if k < node.parent.key:
                node.parent.left = node.right
                node.right.parent = node.parent
            else:
                node.parent.right = node.right
                node.right.parent = node.parent
        elif not node.right:
            if k < node.parent.key:
                node.parent.left = node.left
                node.left.parent = node.parent
            else:
                node.parent.right = node.left
                node.left.parent = node.parent
        else:
            temp = node.right
            while temp.left:
                temp = temp.left
            if temp != node.right:
                if temp.right:
                    temp.parent.left = temp.right
                    temp.right.parent = temp.parent
                temp.parent = node.parent
                temp.left = node.left
                temp.right = node.right
                node.left.parent = temp
                node.right.parent = temp
                if node != self.root:
                    if k < node.parent.key:
                        node.parent.left = temp
                    else:
                        node.parent.right = temp
                else:
                    self.root = temp
            else:
                temp.left = node.left
                node.left.parent = temp
                temp.parent = node.parent
                if node != self.root:
                    if node == node.parent.left:
                        node.parent.left = temp
                    else:
                        node.parent.right = temp
                else:
                    self.root = temp

    def sucessor(self, k):
        node = self.search(k)
        if node.right:
            temp = node.right
            while temp.left != None:
                temp = temp.left
            return temp
        else:
            temp = node.parent
            while temp != None and temp.key < k:
                temp = temp.parent
            if not temp:
                return 0
            else:
                return temp.key

    def predecessor(self, k):
        node = self.search(k)
        if node:
            if node.left:
                temp = node.left
                while temp.right:
                    temp = temp.right
                return temp
            else:
                if node.parent:
                    if node.parent.key < k:
                        return node.parent.key
                return 0
        else:
            print('Node with key \"{}\" not found.'.format(k))