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
|
class Node:
key = 0
value = 0
left = 0
right = 0
size = 0
class BST:
root = Node
def size(self):
return self.size(self.root)
def size(self, node):
return node.size
def get(self, key):
return self.get(self.root, key)
def get(self, node, key):
if node == None:
return
if key < node.key:
return self.get(node.left, key)
elif key > node.key:
return self.get(node.right, key)
return node.value
def put(self, key, value):
return self.put(self.root, key, value)
def put(self, node, key, value):
if key < node.key:
self.put(node.left, key, value)
elif key > node.key:
self.put(node.right, key, value)
node.value = value
node.size = self.size(node.left) + self.size(node.right) + 1
return node
def max(self):
return self.max(self.root)
def max(self, node):
if node.right == None:
return node
return self.max(node.right)
def min(self):
return self.min(self.root)
def min(self, node):
if node.left == None:
return node
return self.min(node.left)
def floor(self, key):
return self.floor(self.root, key)
def floor(self, node, key):
if key == node.key:
return node
if key < node.key:
return self.floor(node.left, key)
if node.right == None:
return node
nextNode = self.floor(node.right, key)
if nextNode == None:
return node
return nextNode
def ceiling(self):
pass
def select(self, rank):
return self.select(self.root, rank)
def select(self, node, rank):
size = self.size(node.left)
if size > rank:
return self.select(node.left, rank)
elif size < rank:
return self.select(node.right, rank - size -1)
else:
return rank
def rank(self, key):
return self.rank(self.root, key)
def rank(self, node, key):
if node.key < key:
return self.rank(node.left, key)
elif node.key > key:
return 1 + self.size(node.left) + self.rank(node.right, key)
else:
return self.size(node.left)
def deleteMin(self):
return self.deleteMin(self.root)
def deleteMin(self, node):
if node.left == None:
return node.right
node.left = self.deleteMin(node.left)
node.size = self.size(node.left) + self.size(node.right) + 1
return node
def delete(self, key):
return self.delete(self.root, key)
def delete(self, node, key):
if key < node.key:
node.left = self.delete(node.left, key)
elif key > node.key:
node.right = self.delete(node.right, key)
else:
if node.right == None:
return node.left
if node.left == None:
return node.right
tmpNode = node
node = self.min(tmpNode.right)
node.right = self.deleteMin(tmpNode.right)
node.left = tmpNode.left
node.size = self.size(node.left) + self.size(node.right) + 1
return node
def keys(self):
queue = []
self.keys(self.root, queue, self.min(), self.max())
return queue
def keys(self, node, queue, lo, hi):
if lo < node.key:
self.keys(node.left, queue, lo, hi)
if lo <= node.key & lo >= node.key:
queue.append(node.key)
if lo > node.right:
self.keys(node.right, queue, lo, hi)
|
