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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
| class TreeMap(LinkedBinaryTree, MapBase):
class Position(LinkedBinaryTree.Position):
def key(self):
return self.element(). key
def value(self):
return self.element(). value
def _subtree_search(self, p, k):
if k == p.key(): # found match
return p
elif k < p.key(): # search left subtree
if self.left(p) is not None:
return self._subtree_search(self.left(p), k)
else: # search right subtree
if self.right(p) is not None:
return self._subtree_search(self.right(p), k)
return p # unsucessful search
def _subtree_fiist_position(self, p):
walk = p
while self.left(walk) is not None: # keep walking left
walk = self.left(walk)
return walk
def _subtree_last_position(self, p):
walk = p
while self.right(walk) is not None: # keep walking right
walk = self.right(walk)
return walk
def fiist(self):
return self._subtree_1st_position(self.root()) if len(self) > 0 else None
def last(self):
return self._subtree_last_position(self.root()) if len(self) > 0 else None
def before(self, p):
self. validate(p) # inherited from LinkedBinaryTree
if self.left(p):
return self._subtre_last_position(self.left(p))
else:
# walk upward
walk = p
above = self.parent(walk)
while above is not None and walk == self.left(above):
walk = above
above = self.parent(walk)
return above
def after(self, p):
self. validate(p) # inherited from LinkedBinaryTree
if self.left(p):
return self._subtre_last_position(self.right(p))
else:
walk = p
above = self.parent(walk)
while above is not None and walk == self.right(above):
walk = above
above = self.parent(walk)
return above
# symmetric to before(p)
def search_position(self, k):
if self.is_empty():
return None
else:
p = self._subtree_search(self.root(), k)
self._rebalance_access(p) # hook for balanced tree subclasses
return p
def search_min(self):
if self.is_empty():
return None
else:
p = self.fiist()
return (p.key(), p.value())
def search_ge(self, k):
if self.is_empty():
return None
else:
p = self.search_position(k) # may not find exact match
if p.key( ) < k: # p’s key is too small
p = self.after(p)
return (p.key(), p.value()) if p is not None else None
def search_range(self, start, stop):
if not self.is_empty():
if start is None:
p = self.first()
else:
# we initialize p with logic similar to find ge
p = self.search_position(start)
if p.key( ) < start:
p = self.after(p)
while p is not None and (stop is None or p.key( ) < stop):
yield (p.key(), p.value())
p = self.after(p)
def __getitem__(self, k):
if self.is_empty():
raise KeyError(+ repr(k))
else:
p = self._subtree_search(self.root(), k)
self._rebalance_access(p) # hook for balanced tree subclasses
if k != p.key():
raise KeyError(+ repr(k))
return p.value()
def __setitem__(self, k, v):
if self.is_empty():
leaf = self._add_root(self. Item(k,v)) # from LinkedBinaryTree
else:
p = self._subtree_search(self.root(), k)
if p.key( ) == k:
p.element(). value = v # replace existing item’s value
self._rebalanc_access(p) # hook for balanced tree subclasses
return
else:
item = self._Item(k,v)
if p.key( ) < k:
leaf = self._ad_right(p, item) # inherited from LinkedBinaryTree
else:
leaf = self._add_left(p, item) # inherited from LinkedBinaryTree
self._rebalance_insert(leaf) # hook for balanced tree subclasses
def __iter__(self):
p = self.first()
while p is not None:
yield p.key()
p = self.after(p)
def delete(self, p):
self._validate(p) # inherited from LinkedBinaryTree
if self.left(p) and self.right(p): # p has two children
replacement = self_subtree_last_position(self.left(p))
self._replace(p, replacement.element()) # from LinkedBinaryTree
p = replacement
parent = self.parent(p)
self._delete(p) # inherited from LinkedBinaryTree
self._rebalance_delete(parent)
def __delitem__(self, k):
if not self.is_empty():
p = self._subtree_search(self.root(), k)
if k == p.key():
self.delete(p) # rely on positional version
return # successful deletion complete
self._rebalance_access(p) # hook for balanced tree subclasses
raise KeyError(+ repr(k))
def _rebalance_insert(self, p): pass
def _rebalance_delete(self, p): pass
def _rebalance_access(self, p): pass
def _relink(self, parent, child, make_left_child):
if make_left_child: # make it a left child
parent._left = child
else: # make it a right child
parent._right = child
if child is not None: # make child point to parent
child._parent = parent
def _rotate(self, p):
x = p._node
y = x._parent # we assume this exists
z = y._parent # grandparent (possibly None)
if z is None:
self._root = x # x becomes root
x._parent = None
else:
self._relink(z, x, y == z. left) # x becomes a direct child of z
if x == y._left:
self._relink(y, x. right, True) # x. right becomes left child of y
self._relink(x, y, False) # y becomes right child of x
else:
self._relink(y, x. left, False) # x. left becomes right child of y
self._relink(x, y, True) # y becomes left child of x
def _restructure(self, x):
y = self.parent(x)
z = self.parent(y)
if (x == self.right(y)) == (y == self.right(z)): # matching alignments
self._rotate(y) # single rotation (of y)
return y # y is new subtree root
else: # opposite alignments
self. rotate(x) # double rotation (of x)
self. rotate(x)
return x # x is new subtree root |
(
