def _subtree_search(self, p, k):
"""搜索算法"""
if k == p.key():
return p
elif k < p.key():
if self.left(p) is not None:
return self._subtree_search(self.left(p), k)
else:
if self.right(p) is not None:
return self._subtree_search(self.right(p), k)
return p
def _subtree_first_position(self, p):
"""返回树的最左节点"""
walk = p
while self.left(walk) is not None:
walk = self.left(walk)
return walk
def _subtree_last_position(self, p):
"""返回树的最右节点"""
walk = p
while self.right(walk) is not None:
walk = self.right(walk)
return walk
下面是一些公开的访问方法：
def first(self):
return self._subtree_first_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):
"""前驱位置"""
if self.left(p):
return self._subtree_last_position(self.left(p))
else:
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):
"""后继位置"""
if self.right(p):
return self._subtree_first_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
def find_position(self,k):
if self.is_empty():
return None
else:
p = self._subtree_search(self.root(),k)
return p
接下来是映射的核心方法：
def __getitem__(self, k):
if self.is_empty():
raise KeyError('Key Error'+repr(k))
else:
p = self._subtree_search(self.root(),k)
if k!=p.key():
raise KeyError('Key Error' + repr(k))
return p.value()
def __setitem__(self, k,v):
if self.is_empty():
leaf = self.add_root(self._Item(k,v))
else:
p = self._subtree_search(self.root(),k)
if p.key() == k:
p.element().value = v
return
else:
item = self._Item(k,v)
if p.key() < k:
leaf = self.add_right(p,item)
else:
leaf = self.add_left(p, item)
def __iter__(self):
p = self.first()
while p is not None:
yield p.key()
p = self.after(p)
def mapdelete(self,p):
if self.left(p) and self.right(p): #两个孩子都有的时候
replacement = self._subtree_last_position(self.left(p)) #用左子树最右位置代替
self.replace(p,replacement.element())
p = replacement
self.delete(p)
def __delitem__(self, k):
if not self.is_empty():
p = self._subtree_search(self.root(),k)
if k == p.key():
self.mapdelete(p)
return
raise KeyError('Key Error' + repr(k))
最后是一些有序映射特有的方法：