-
Notifications
You must be signed in to change notification settings - Fork 126
/
BinarySearchTree.py
106 lines (91 loc) · 2.62 KB
/
BinarySearchTree.py
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
import random
class Tree:
def __init__(self):
self.l = None
self.r = None
self.k = None
self.p = None
def Transplant(self, u, v):
if u.p is None:
u.k = v.k
elif u is u.p.l:
u.p.l = v
else:
u.p.r = v
if v.k is not None:
v.p = u.p
def TreeDelete(self, z):
if z.l.k is None:
self.Transplant(z, z.r)
elif z.r.k is None:
self.Transplant(z, z.l)
else:
y = z.r.TreeMinimum()
if y.p is not z:
self.Transplant(y, y.r)
y.r = z.r
y.r.p = y
self.Transplant(z, y)
y.l = z.l
y.l.p = y
def Insert(self, T, i, P):
if T.k == None:
T.k = i
T.p = P
T.l = Tree()
T.r = Tree()
elif T.k > i:
self.Insert(T.l, i, T)
elif T.k < i:
self.Insert(T.r, i, T)
def Sort(self, A):
# random.shuffle(A) # This is use to get randomized Tree.
for i in range(0, len(A)):
self.Insert(self, A[i], None)
def InOrderTreeWalk(self, A):
if self.k is not None:
self.l.InOrderTreeWalk(A)
A.append(self)
self.r.InOrderTreeWalk(A)
def TreeSearch(self, k):
if self.k == k or self.k is None:
return self
elif k < self.k:
return self.l.TreeSearch(k)
else:
return self.r.TreeSearch(k)
def IterativeTreeSearch(self, k):
while self.k is not None and self.k != k:
if k < self.k:
self = self.l
else:
self = self.r
return self
def TreeMinimum(self):
while self.l.k is not None:
self = self.l
return self
def TreeMaxinum(self):
while self.r.k is not None:
self = self.r
return self
A = []
s = random.randint(5, 100)
for i in range(0, s):
A.append(random.randint(0, 1000))
k = random.choice(A)
t = Tree()
t.Sort(A)
A = []
t.InOrderTreeWalk(A)
print "Using InOrderWalk:", [A[i].k for i in range(0, len(A))]
print "Using Recursion method to find ", k, " :", t.TreeSearch(k).k
print "Using Interval method to find ", k, " :", t.IterativeTreeSearch(k).k
print "Finding the Minimum elem :", t.TreeMinimum().k
print "Finding the Maximum elem :", t.TreeMaxinum().k
d = random.choice([A[i].k for i in range(len(A))])
print "we are going to delete:",d
t.TreeDelete(t.TreeSearch(d))
B = []
t.InOrderTreeWalk(B)
print "After deletion:",[B[i].k for i in range(0, len(B))]