第十一章

本章叙述了不同平衡树的构造性能问题

习题代码如下(部分代码引用书中源代码，源代码位置目录在第二章答案中介绍)

#11.1#(1,A)# \# (2,B)# \# (3,C)# \# (4,D)#\#(5,E)#11.2 详细图略# 30# / \#2440# / \ \# 11 2658# \ /# 13 48#11.3 四种# //\\#/\/\#11.4 (1,2,3,4) 和 (3,2,1,4)#11.5 (3,4,2,1) 和 (1,2,3,4)#11.6def text6(self,p,k):while p.key()!=k:if p.key()>k: # search the left subtreeif self.left(p) is None:breakp=self.left(p)elif p.key()<k: # search the right subtreeif self.right(p) is None:breakp=self.right(p)return p#11.7 图11-12是自旋转两次 图11-14是自旋转一次#11.8# 62# /\# 50 78# /\ \#44 54 88# / \/# 17 48 52#11.9# 54# /\# 44 78# /\ \#17 50 88# / \# 48 54#11.10 在一颗用数组方式存储的二叉树中,这棵树的任意一个节点的位置通过父节点在数组中的索引计算得到的#如果一个父节点需要交换位置，那么特的孩子节点也需要交换到其他的位置#11.11 用(T,D)表示每个节点、T:树的名称 D:树的深度#删除前:# (z,h+2)# /\# (t1,h) (y,h+1)# /\#(t2,h) (x,h) # / \# (t3,h-1) (t4,h-1)#删除后:z出现不平衡# (z,h+2)#/ \# (t1,h-1) (y,h+1)# /\#(t2,h) (x,h) # / \# (t3,h-1) (t4,h-1)#旋转:#(y,h+2)#/ \# (z,h+1) (x,h)# / \/\# (t1,h-1) (t2,h) (t3,h-1) (t4,h-1)#11.12 #删除前:# (z,h+2)# /\# (t1,h) (y,h+1)# /\# (x,h) (t4,h-1)# / \# (t2,h-1) (t3,h-1)#删除后:z出现不平衡# (z,h+2)# /\# (t1,h-1) (y,h+1) # /\#(x,h)(t4,h-1)#/ \# (t2,h-1)(t3,h-1)#第一次旋转:# (z,h+2)# / \# (t1,h-1) (x,h+1)#/ \#(t2,h-1)(y,h)# /\# (t3,h-1) (t4,h-1)#第二次旋转:#(x,h+1)#/ \# (z,h) (y,h)# / \/\# (t1,h-1) (t2,h-1) (t3,h-1) (t4,h-1)#11.13 在trindoe时,直接出现不平衡#删除前:# (z,h+2)# /\# (t1,h) (y,h+1)# /\#(x,h) (t4,h) #/ \#(t2,h-1) (t3,h-1)#删除后:# (z,h+2)# /\# (t1,h-1) (y,h+1)# /\#(x,h) (t4,h) #/ \#(t2,h-1) (t3,h-1)#第一次旋转:在x处出现不平衡# (z,h+2)# /\# (t1,h-1) (x,h+2)#/\#(t2,h-1)(y,h+1)# /\# (t3,h-1) (t4,h)#11.14 只给出最终图形#a:# 18#/# 16# /# ···# /# 0#b: # 18#/# 16# /# ···# /# 0# \#2#c:略#11.15 不知如何描述问题的答案,上了chegg网查询#查询出的答案是关于splay树的存储,会让最大的元组在树的根部,其次每个元素都在父节点的左部(但是access有存取也有访问的意思)#如果是顺序访问的话根据上一题画的图,大部分节点也会在其父节点的左孩子节点上#11.16 不是(2,4)树需要满足两个条件:A 每个节点最多只能有四个自节点,最少两个自节点;B 每个外部节点的深度一样#11.17 将k2存入w的父节点中# (k1,k2,k3,k4) 需要将其分为两部分,第一部分一个节点,第二部分两个节点;# 因为需要一个比第一部分大,又比第二部分小的值.所以只有k2,k3 能够满足大小关系# 因为第一个部分一个节点,第二部分两个节点.所以需要将k2放入w中.#11.18#{1,2,3,4,5}#2# / \# 1 (3,4,5)#{5,4,3,2,1}#4# / \# (1,2,3) 5#11.19 当存在两个或者两个以上个3-node节点,就可以画出多个不同的红黑树对应相同的(2,4)树#11.20# 1):每个节点都是4-node#(4，8，12 )# /| |\#(1,2,3)(5,6,7)(9,10,11)(13,14,15)# 2):每个节点都是2-node 构成完全二叉树 略#11.21# 1): ( 5 , 16 , 22 )# / | | \# (1,2)(10,12) (18)(30,45,50)# 2): (N,C) N: 键值 C: 颜色# (16,b)# / \# (5,r)(22,r)# /\ /\# (2,b) (10,b) (18,b)(45,b)# / \ /\#(1,r) (12,r) (30,r)(50,r)#11.22# a):F,红黑树的任意以黑色节点为根节点的子树为红黑树# b):T,当一个节点没有兄弟节点时,他的父节点只有一个节点,需要满足(只有一个子节点、没有子节点)的黑色深度相同# 也就是说这个节点要和父节点有相同的黑色深度,所以这个节点必须为红色节点.# c):T:多棵红黑树对应一颗(2,4)树,取决于红黑树中3-node节点个个数,(2,4)树中的一个3-node节点对应两种红黑的形式.# d):F:c中已解释#11.23# 三种树结构,是对旋转的不同使用结果;在旋转结束后,每个节点映射到水平线上位置不发生改变;# 中序遍历是从左向右进行遍历,所以不会改变中序遍历结果#11.24# 1): 100000 #按大小顺序插入# 2): log(100000)# 3): 100000 #按大小顺序插入# 4): log(100000)# 5): log(100000)#11.25 (N,C,H) N:为键值 C:为颜色(b,r) H:为深度#(4,b,4)# /\# (3,b,1)(7,r,3)#/\#(5,b,2) (8,b,1)#\# (6,r,1)#11.26 在红黑树中,一个节点A如果只有一个叶子节点,那么这个叶子节点和节点A是要有相同的黑色高度的# 所以叶子节点应该为红色,A应该为黑色#11.27 在删除之前,p有两个叶子节点a,b;为了保证两个叶子节点黑色深度,当a是红色时，b一定时红色,当b时黑色时,a一定时黑色;#在删除之后,p有一个叶子节点,所以如果被保留的叶子节点是黑色时,就会因为需要节点p和它被保留的黑色子节点深度相同,破坏黑色深度#11.28 在删除之前,p有两个叶子节点a,b,并且b有一个左子节点c,# 此时保证了a,b,c三节点的黑色深度相同,就需要c为红色,所以a,b为黑色#删除b后,p还是拥有两个子节点#11.29 红黑树和AVL树的高度都保持在log(n),所以直接将序列逐个插入就可以实现# O(h*2^(h-1)的求和,1<=h<=log(n) )=O(n*(logn-1/2)-1)#11.30 可以伸展树的摊销运行时间为O(logn) 即使在最坏的情况下,搜索一个元素的时间需要O(n),但是摊销后还是log(n)#11.31 将__setitem__方法修改即可from TheCode.ch11.binary_search_tree import TreeMapclass BST1(TreeMap):def setdefaut(self,k,v):''' return k's value if k exist in the tree,else add (k,d)'''if self.is_empty():leaf = self._add_root(self._Item(k, v))# from LinkedBinaryTreeelse:p = self._subtree_search(self.root(), k)if p.key() == k:return p.element()._valueelse:item = self._Item(k, v)if p.key() < k:# inherited from LinkedBinaryTreeleaf = self._add_right(p, item)else:# inherited from LinkedBinaryTreeleaf = self._add_left(p, item)# hook for balanced tree subclassestry:# add try grammar for text the ADTself._rebalance_insert(leaf)except e:pass#t=BST1()#for i in range(5):# t.setdefaut(i,i)#print(t.setdefaut(i,i+10))#11.32#树的旋转:# | |# y x#/ \<==> / \# x t3t1 y# / \/ \# t1 t2t2 t3#在树中,通过每两个节点之间的位置关系,使二叉树有不同的形状,但都可以通过旋转的方式改变树的整体结构#11.33#当我们寻找一个节点的最大的lt时 A:如果这个节点有孩子节点,我们找到左孩子的最右节点,# 如果没有孩子节点,向上寻找父节点,知道找到一个小于自己的父节点#当我们寻找一个节点的最小的gt时 B:如果这个节点有孩子节点,我们找到右孩子的最左节点,# 如果没有孩子节点,向上寻找父节点,知道找到一个大于自己的父节点#当我们没有找到k时,可以将k看成没有孩子节点的情况,所以他的A、和B都在他的父节点上#11.34# after()时间复杂度保证在O(h)内,在最坏的情况下从树的根节点遍历到树的叶子节点;# 但在find_range()方法中最坏的情况只发生一次,其余时间复杂度度为O(1)#11.35# 提要:在删除根节点或者只有一个孩子的节点时,可以直接删除,不需要寻找其他节点替换# 将需要删除的节点分为两部分,start(第一个节点)和another(除第一个节点以外其余节点)# A:在another中的第一个节点一定为整棵树的某个叶子节点或只有一个孩子的节点(大于start的最小节点)# B:another中的第二个节点为A中找到节点的父节点(如果A中找到的是叶子节点)或者A中找到节点的右节点的最左节点(如果A只有一个孩子的节点,回到A)# C:another中的第三个节点为A中找到节点的父节点的右节点(如果A中找到的是叶子节点),等等# 在理想情况下:A和C为B的左右节点,先删除A和C然后在删除B,向上递归删除,# 非理想情况下:也是从叶子结点开始向上删除(还是按照从下向上删除节点)# 最后可能会存最上面的节点有左右孩子,所以需要使用小的最大的节点来替换这个节点来删除# 助理root节点#11.36# 在AVL树中,每删除一个节点都需要向上查找是否出现不平衡，所以时间复杂度为O(slogN)#11.37#在每个节点加入以该节点为根的所有自节点个数#还要修改对应的增加和删除,每次操作后都需要更新祖父节点中记录的值#以下是查找算法#Algorithm(star,stop):# find first node: start<=node's<=stop# s=sum of node's child num# big=node'right {right node mark the max num}# small=node'left {left node mark the min mum}# repeat:{cut down the branch which beyond the range}# if big!=None: # if big<=stop:#big=big.right# else:#sum-=sum of big's right child num and 1#big=big.right# if small!=None:# if small>=start:#small=small.left# else:#sum-=sum of small's left child num and 1#small=small.right # untill: big and small are None# return sum#11.38 需要修改_Node中存储子节点的个数# 在_relink方法中修改#11.39 分为三部分,前那两部分构成严格意义的log(n)的时间# part1:寻找节点k {k深度的时间}# part2:寻找比k节点小的最大节点 {从k的深度开始向下,直到树的根部}# part3:被删除的节点可能会造成树高度不平衡,需要trinode {可能为1可能为log(n)}#ps:trinode为rotation之后树的高度有所减小,树变得更广泛;rotation是一个只改变位置不改变高的的操作#11.40# 1.平衡因子通过计算获得# 2.根据父节点平衡因子的正负决定左旋还是右旋# 3.在rotate方法中，重新计算旋转改变的平衡因子,在_rebalance中计算改变增加节点改变的平衡因子from TheCode.ch11.avl_tree import AVLTreeMapclass FactorAVL(AVLTreeMap):'''alter variable:_heightalter method:left_heightright_height_recompute_height_isbalanced_tall_child_rebalance_rotate'''class _Node(AVLTreeMap._Node):__slots__ = '_factor' # additional data member to store heightdef __init__(self, element, parent=None, left=None, right=None):super().__init__(element, parent, left, right)self._factor = 0 # will be recomputed during balancingdef left_factor(self):return self._left._factor if self._left is not None else 0def right_factor(self):return self._right._factor if self._right is not None else 0#------------------------- positional-based utility methods --------------def _recompute_factor(self, p,orient):''' have aid of the orient parameter'''if orient==None:return p._node._factor =p._node._factor+1 if orient=='l' else p._node._factor-1def _isbalanced(self, p):return p._node._factor!=2 or p._node._factor!=-2 # return False when factor== 2 or -2def _tall_child(self, p, favorleft=False): # parameter controls tiebreakerif p._node.left_factor() + (1 if favorleft else 0) > p._node.right_factor():return self.left(p)else:return self.right(p)def _tall_grandchild(self, p):child = self._tall_child(p) # 子孩子一定有一个节点高# if child is on left, favor left grandchild; else favor right# grandchildalignment = (child == self.left(p))return self._tall_child(child, alignment)def _rebalance(self, p):orient=None # definition the orient of child,'l' if leftchild else 'r'while p is not None:old_height = p._node._height# trivially 0 if new node self._recompute_factor(p,orient)# imbalance detected!if not self._isbalanced(p):# perform trinode restructuring, setting p to resulting root,# and recompute new local heights after the restructuringp = self._restructure(self._tall_grandchild(p))# adjust for recent changes if p._node._height == old_height and orient==None:# has height changed?p = None # no further changes neededelse:# cheak the orientsif p is self.parent(p).left():orient='l'else:orient='r'# repeat with parentp = self.parent(p)def _rotate(self, p):"""Rotate Position p above its parent.Switches between these configurations, depending on whether p==a or p==b.y y/ \/ \x t2 t0 x/ \ / \t0 t1 t1 t2Caller should ensure that p is not the root.""""""Rotate Position p above its parent."""x = p._nodey = x._parent # we assume this exists# grandparent (possibly None)z = y._parentif z is None:self._root = x# x becomes rootx._parent = Noneelse:# x becomes a direct child of zself._relink(z, x, y == z._left)# now rotate x and y, including transfer of middle subtreeif x == y._left:# x._right becomes left child of yself._relink(y, x._right, True)# y becomes right child of xself._relink(x, y, False)#calculate the factory._factor=y._factor+min(-x._factor,0)+1x._factor=x._factor+min(0,y._factor)-1else:# x._left becomes right child of yself._relink(y, x._left, False)# y becomes left child of xself._relink(x, y, True)#calculate the factory._factor=y._factor+max(-y._factor,0)+1x._factor=x._factor+max(0,y._factor)+1#text11.40#t=FactorAVL()#for i in range(20):# t[i]=i#for i in range(20):# print(t[i])#11.41 围绕树的增、删、改、查,对函数进行更改#增:通过对比新增的节点大小关系，来更新最小值的指针#删:通过判断删除的节点是否为指针指向节点,来更新指针,若为最小值,则进行中序遍历#改:修改只会更改键值对应的内容,所以此部分不需要修改#查:将与获取树最小节点有关的方法使用find_min代替#11.42 AVL树不需要进行更改from TheCode.ch11.avl_tree import AVLTreeMapclass LeftAVL(AVLTreeMap):'''add a filed to store the minium node,it's a position class;control the minimum node when add node or delete node'''#-----------------------------add a filed----------------------------------def __init__(self):super().__init__()self._mininum=None# a Position class#-----------------------------control the mininum----------------------------------def _add_root(self,k,v):temp=super()._add_root(k,v)if k==None or k<self._mininum.element()._key:self._mininum=tempreturn tempdef _add_left(self,k,v):temp=super()._add_left(k,v)if k==None or k<self._mininum.element()._key:self._mininum=tempreturn tempdef _add_right(self,k,v):temp=super()._add_right(k,v)if k==None or k<self._mininum.element()._key:self._mininum=tempreturn temp'''def _rebalance_insert(self,p):if self._mininum==None or p.element()._key<self._mininum.element()._key:self._mininum=psuper()._rebalance_insert(p)'''def __delitem__(self,k):''' remove the node which values equal k'''if k==self._mininum.element()._key:self._muninum=self.after(self._mininum)super().__delitem__(k)def _subtree_first_position(self, p):"""Return Position of first item in subtree rooted at p."""return self._mininum#text11.42 #t=LeftAVL()#for i in range(20,10,-1):# t[i]=i# #print(t._mininum)# print(t.first().element()._key)#for i in range(11,21):# del t[i]# print('del',i)# print(t.first().element()._key)#11.43 直接在AVLTreeMap树上使用from TheCode.ch11.avl_tree import AVLTreeMapclass AFAVL(AVLTreeMap):'''add a field to make after and before method worst-cost O(1)-time;'''#-----------------------------add a filed----------------------------------class _Node(AVLTreeMap._Node):__slots__ = '_before','_after' # additional data member to store heightdef __init__(self, element, parent=None, left=None, right=None,before=None,after=None):super().__init__(element, parent, left, right)self._before=beforeself._after=after#-----------------------------alter add method---------------------------------- def _add_left(self,p,e):''' inherit from linked_binary_tree'''temp=super()._add_left(p,e)node = self._validate(temp)p=node._parent # get the parent nodenode._after=p # tie the nodenode._before=p._beforeif p._before !=None:# if p is the mininum value nodenode._before._after=nodenode._after._before=nodereturn tempdef _add_right(self,p,e):''' inherit from linked_binary_tree'''temp=super()._add_right(p,e)node = self._validate(temp)p=node._parent # get the parent nodenode._before=p # tie the nodenode._after=p._afterif p._after != None: # if p is the maxnum value nodenode._after._before=nodenode._before._after=nodereturn temp#-----------------------------alter delete method---------------------------------- def _delete(self,p):''' inherit from linked_binary_tree'''temp=super()._delete(p)temp._after._before=temp._before # tie the nodetemp._before._after=temp._afterdef after(self,p):node=self._validate(p) # inherited from LinkedBinaryTreereturn self._make_position(node._after)def before(self,p):node=self._validate(p)return self._make_position(node._before)#text11.43#t=AFAVL()#for i in range(20):# t[i]=i# print(i)#temp=t.first()#for i in range(19):# temp=t.after(temp)# print(temp)#print('#####')#for i in range(20):# temp=t.before(temp)# print(temp)#11.44 如上提代码,无需修改#11.45 delete(p)方法需要找到比p小的最大节点,在找节点的过程中消耗了O(h),在修改过后,可以在O(1)的时间内找到该节点#11.46 新增两个field存储当前节点左右自节点个数,通过计算节点数来得到索引from TheCode.ch11.binary_search_tree import TreeMapclass SupplementTM(TreeMap):'''add two field '''#-----------------------------alter two field---------------------------------- class _Node(TreeMap._Node):''' inherit from linked_binary_tree '''__slots__='_left_num','_right_num'def __init__(self,element, parent=None, left=None, right=None,_left_num=0,_right_num=0):super().__init__(element, parent, left, right)self._right_num=_right_num # add field for sum of right child numself._left_num=_left_num# add field for sum of left child numclass Position(TreeMap.Position):''' inherit from linked_binary_treeadd two methods for coding conveniently'''def left_num(self):return self._node._left_num # return def right_num(self): return self._node._right_numdef _change_num(self,temp,num):''' temp is the beginning node which is a Position class,num is the int where need to change;node's num on the route which from node p to root add num'''p=self.parent(temp)while p is not None: # cycle to add the child numif temp is self.left(p): # if p is left child ,parent._left_num+=1p._node._left_num+=numelse: # else p is right child, parent._right_num+=1p._node._right_num+=numtemp=pp=self.parent(p)#-----------------------------alter add method---------------------------------- def _add_left(self,p,e):temp=super()._add_left(p,e)self._change_num(temp,1)# node's num on the route which from node p to root add 1 def _add_right(self,p,e):temp=super()._add_right(p,e)self._change_num(temp,1)# node's num on the route which from node p to root add 1 #-----------------------------alter delete method---------------------------------- def _delete(self,p):self._change_num(p,-1) # node's num on the route which from node p to root add -1super()._delete(p)#-----------------------------add method----------------------------------def at_index(self,i,p=None):''' recursion compare the child's num with i to get the Positionindex range begin at 0'''if i >=self._size or i<0:raise KeyError('invalid key')if p==None: p=self._root# recur from the root nodeif i<p._left_num:# if index i in p's left subtreereturn self.at_index(i,p._left)elif i == p._left_num:return self._make_position(p) # if index i is pelse:return self.at_index(i-p._left_num-1,p._right) # if index i in p's right subtreedef index_of(self,p):''' cycle compare the child parent with itself's position to get the indexp is a Position class'''num=p.left_num()if p is self.root(): # if p is rootreturn numtemp=self.parent(p) # record the parent nodewhile temp !=None:if p == self.right(temp): # if p is it's parent's right nodenum+=temp.left_num()+1 # num += left subtree node and 1p=temptemp=self.parent(temp)return num#text11.46#t=SupplementTM()#for i in range(10,30):# t[i]=i#temp=t.root()#for i in range(10,30):# print(temp.left_num(),temp.right_num())# temp=t.after(temp)#for i in range(20):# temp=t.at_index(i)# print(temp.element()._key)# print(t.index_of(temp))#11.47#按range(1,11)的顺序添加元素#伸展树:# 10#/# 9# /# 8#/# ···# /#0#红黑树:1b为黑色的值为1的节点 10r为红色的值为10的节点# 4b# /\# 2b 6b# / \/ \#1b3b5b8r# / \# 7b9b# \#10r#11.48 如图(D,h+2代表D节点深度为h+2),在A节点处插入节点导致B节点出现不平衡,但并不导致D出现不平衡# D,h+2# / \# B,h E,h+1# / \# A,h-1 C,h-2#11.49 如图(D,h+2代表D节点深度为h+2),在删除C或者B这种比兄弟节点深度小的节点时,才会出现不平衡,# 但因为父节点的深度取决于比较高的孩子节点,所以不平衡不会向上传递# D,h+2# / \# B,h E,h+1# / \# A,h-1 C,h-2#11.50 书中翻译错误,应为T中的所有键的值小于U中所有键的值#1) 将U中最左边的节点或者T中最右边的节点pop,记为e(不能破坏2-3-4的性质)#2) if h(T)<h(U): # 从U的最左边向上travel,当U中节点的深度等于T的高度# 在当前节点中添加e,令T成为e的左子树# 此时为所需要的2-3-4树# if h(T)>h(U): # 从T的最右边向上travel,当T中节点的深度等于U的高度# 在当前节点中添加e,令U成为e的右子树# 此时为所需要的2-3-4树# if h(T)=h(U):# 令e成为T,U的父节点# 此时就是所需要的2-3-4树#11.51#1) 在T树中寻找最右节点,并记录路径中遇到的黑色节点数目极为n,#2) 在U树中寻找最左节点,并记录路径中遇到的黑色节点数目极为m#3) 将U中最左边的节点或者T中最右边的节点pop,记为e(不能破坏红黑树的性质)#4) if n=m： # 将e涂黑,令T、U分别为e的左右子树# 此时就是所需要的红黑树# if n<m:# 从U的最左边向上travel并记录路径中遇到的黑节点个数为t,当t=n+1,停止travel# 将e涂红,令当前节点的左孩子为e的右孩子,T为e的左孩子(注意染色问题)# 此时就是所需要的红黑树# if n>m:# 从T的最右边向上travel并记录路径中遇到的黑节点个数为t,当t=m+1,停止travel# 将e涂红,令当前节点的右孩子为e的左孩子,U为e的右孩子(注意染色问题)# 此时就是所需要的红黑树#11.52#证明:当以下节点为叶子节点时# 2-node节点,有两个外部节点,会多出一个外部节点,将多出的外部节点向上传递# 3-node节点,有三个外部节点,会多出一个外部节点,将多出的外部节点向上传递# 4-node节点,有四个外部节点,会多出一个外部节点,将多出的外部节点向上传递# 当以下节点不为叶子节点时# 2-node节点,得到传递的两个外部节点,会多出一个外部节点,将多出的外部节点向上传递# 3-node节点,得到传递的三个外部节点,会多出一个外部节点,将多出的外部节点向上传递# 4-node节点,得到传递的四个外部节点,会多出一个外部节点,将多出的外部节点向上传递#当传递到顶部节点后,最终会多处一个外部节点#11.53#考虑红黑树必须将红节点和黑节点区分#当键不同时,所以在树中创建一个集合用来存储红色节点#在使用时通过判断key在不在集合中来确定当前是红还是节点#11.54#思路:从root节点开始向下travel,当前节点记为walk,判断walk和k之间的大小关系# 如果walk>k:# 将walk右子树使用习题51的方法拼接到T2中# 将walk插入到T2中# 如果walk<k:# 将walk左子树使用习题51的方法拼接到T1中# 将walk插入到T1中# 如果walk==k:# 将walk左子树使用习题51的方法拼接到T1中# 将walk右子树使用习题52的方法拼接到T2中# 将walk删除# return#11.55#根据AVL树的特性,树左右子树的高度相差不超过1#递归的思想:每个节点较高子树比较低子树多一层,可以通过在较高子树中使某一层节点变为红色节点来使两个子树的黑色深度相同# 因为较高子树只比较低子树多一层,所以在保证黑色节点数目相同时,出现一层红一层黑而不会出现双红现象#11.56#algorithm(node,k):# {node is the current node ,k is the }# z=node { the root}# repeat:# if z>k: # y=z.left# if y is None:{ if can't find k}# return y# if y>k: # x=z.left# if x==None: { zig case}#self._rotate(y)# self._rotate(y) { zig-zig case}# self._rotate(x)# elif y<k: # x=z.right# if x==None: { zig case}#self._rotate(y)# self._rotate(x) { zig-zag case}# self._rotate(x)# elif z<k: # y=z.right# if y is None:{ if can't find k} # return# if y>k:# x=y.left# if x==None: { zig case}#self._rotate(y)# self._rotate(x) { zig-zag case}# self._rotate(x)# elif y<k:# x=y.right# if x==None: { zig case}#self._rotate(y)# self._rotate(y) { zig-zig case}# self._rotate(x)# else: { if z node==k}# return#11.57 #半伸展树一个δ<=3(r'(x)-r(x)),与伸展树一样#Δ<=3(r(d/2)-r(x))-d/2+2<=log(n) { r(d/2)是深度为d/2的节点 }#所以一个伸展工作需要的时间开销也为log(n)#11.58# eg:in order { 5,6,7,8,9 }# access order { 5 6 9 5 }#不同的入队顺序有不同的访问顺序,根据每次访问一个元素都会将该元素移到root节点来操作访问顺序#1)我们先画出最终图型记为R;#2)根据输入顺序得出的图形记为T;#3)找到R中的叶子节点记为node;#3)对比R和T,T中找到node,如果T中该节点的孩子和node的孩子不同,访问该孩子节点,让其上升(如果有多层不符合规则的孩子节点,从最底层开始访问)#4)在R中找到node的父节点,重复步骤3#11.59from TheCode.ch11.binary_search_tree import TreeMapdef text59(t=TreeMap()):t[2]=2t[1]=1t[3]=3print('in order input [2,1,3] to the tree')root=t.root()left=t.left(root)right=t.right(root)print('delete the root node which value is 2')t.delete(root)print('delete have done')print('original left:\n\t',left.element()._value,'\n\tcurrent position:\n\t',t.root().element()._value)print('original left == new root:\n\t',left == t.root())# left is the original node, should equal with root after delete rootprint('current root\'s next node:\n\t',t.after(t.root()))print('original\'s after:\n\t',t.after(left)) # error sentence ,the node be a loop because _delete() method in # linked_binary_tree.LinkedBinaryTree's class#text11.59#text59() #11.60 重写delete方法,将原仅更改节点的值变为更改节点的位置from TheCode.ch11.binary_search_tree import TreeMapclass AlterTreeMap(TreeMap):def delete(self,p):"""Remove the item at given Position."""node=self._validate(p) # inherited from LinkedBinaryTreeif self.left(p) and self.right(p): # p has two childrenreplacement = self._subtree_last_position(self.left(p))._node# change section# combine replacement's parent with his childif replacement is replacement._parent._left: replacement._parent._left=replacement._left if replacement._left is not None else replacement._rightelse:replacement._parent._right=replacement._left if replacement._left is not None else replacement._right if node is self._root:# if p is root self._root=replacement# combine the new node replacement._parent=node._parentreplacement._left=node._left replacement._right=node._right# convention for deprecated node node._parent=node node._left=node._right=Noneelse:# now p has at most one childparent = self.parent(p)# inherited from LinkedBinaryTreeself._delete(p)# this method will alter node's chain# if root deleted, parent is None#text11.60 使用11.59的函数测试# text59(AlterTreeMap()) #11.61 两种序列模拟{顺序,乱序}三种方法模拟{set,get,delete}from TheCode.ch11.splay_tree import SplayTreeMap as STMfrom TheCode.ch11.avl_tree import AVLTreeMap as AVLTMfrom TheCode.ch11.red_black_tree import RedBlackTreeMap as RBTMimport syssys.setrecursionlimit(100000) #set the maxinum recursiondef text61_getlist(n=1000):import random''' n is the num of listreturn list1, in order sequencereturn list2, disorder sequence'''list1=[i for i in range(n)]list2=random.sample(range(n*5),n)return list1,list2def text61_time(l=None,T=None):import time''' l is the input sequenceT is the data structure's instancereturn the time'''if l==None or T==None:raise KeyError('invalid parameter.')time1=time.time()for i in l: # perform set methodT[i]=ifor i in l: # perform get methodT[i]for i in l:del T[i] # perform del methodreturn time.time()-time1def text61(n=10000):l1,l2=text61_getlist(n)# if there are too many node, python will breaksplay1=text61_time(l1,STM())splay2=text61_time(l2,STM())avl1=text61_time(l1,AVLTM())avl2=text61_time(l2,AVLTM())rbt1=text61_time(l1,RBTM())rbt2=text61_time(l2,RBTM())print('有序:')print('splay:',splay1)print('a v l:',avl1)print('r b t:',rbt1)print('乱序:')print('splay:',splay2)print('a v l:',avl2)print('r b t:',rbt2)#text11.61:#text61()#11.62 粘贴10.53的代码import randomclass SkipTable:''' key is class int, '''#------------------------------_Chain-----------------------------class _Chain:''' '''#------------------------------_Item------------------------------ class _Item:''' none pre'''def __init__(self,k,v,after,below):''' input (key,value,after,below)'''self._key=kself._value=vself._after=afterself._below=belowdef __eq__(self, other):if isinstance(other,int): # if other is intreturn self._key==otherreturn self._key == other._key # compare items based on their keysdef __ne__(self, other):return not (self == other) # opposite of __eq__def __lt__(self, other):if isinstance(other,int): # if other is int# print(self._key,other)return self._key < otherreturn self._key < other._key # compare items based on their keysdef __gt__(self,other):if isinstance(other,int): # if other is intreturn self._key > otherreturn self._key > other._key #def __le__(self,other):#print(self._key,self._value)if isinstance(other,int): # if other is intreturn self._key <= otherreturn self._key <= other._key ##------------------------------------------------------------def __init__(self):''' create a chain with head and tail'''self._head=self._Item('k_min','v_min',None,None)# the min itemself._tail=self._Item('k_max','v_max',None,None)# the max itemself._head._after=self._tail# conbine the head and tailself._size=0def tail(self):return self._taildef __len__(self):return self._sizedef key(self,item):return item._keydef first(self):return self._headdef after(self,item):return item._afterdef below(self,item):return item._belowdef add_after(self,item,new):''' add (new) after the item,only horizontal'''new._after=item._after item._after=newself._size+=1return newdef del_after(self,item):''' delete after the node,only horizontal'''temp=item._afteritem._after=temp._aftertemp._after=Noneself._size-=1return temp#-----------------------------------------------------------------def __init__(self):self._table=[self._Chain()]# store the skipchainself._size=0 # len of the skipTabledef __setitem__(self,k,v):self.insert(k,v)def __getitem__(self,k):''' get the item or raise error'''index,temp=self.search_before(k)chain=self._table[index]ras=chain.after(temp)if ras._key!=k:raise ValueError('no item')return ras._valuedef __delitem__(self,k):self.delete(k)def __len__(self):return self._sizedef _coin(self):''' return a num of the level the item should be'''times=0while random.randint(0,1)==1:times+=1# if the random is 1 ,times +=1return timesdef search_before(self,k,high=None):''' find the node before item that key is k or like k;return (index,temp)if k in this chain,return the index of chain and item before k;if k not in the chain ,reutrn high and item which in the high level bigger other item but small than k or max item '''#print(k,high,len(self._table))chain=self._table[-1] # the top chaintemp=chain.first() # the min nodeif high==None: # vague search for inserthigh=0for i in range(len(self._table)-1,high-1,-1): # inverse order traver the table#print(chain.tail() is chain.after(temp),temp,temp._value) while chain.after(temp) is not chain.tail() and chain.after(temp)<=k: # if item next node isn't tail or bigger than item if chain.after(temp)==k:return (i,temp)# return index of chain and temp which item is not buttom leveltemp=chain.after(temp)if i==high: # end of the tablereturn (i,temp)temp=chain.below(temp) # change the chain chain=self._table[i-1]def append_chain(self):''' append a new chain and conbine the head and tail'''self._table.append(self._Chain())self._table[-1]._head._below=self._table[-2]._head self._table[-1]._tail._below=self._table[-2]._taildef insert(self,k,v):''' caculate the times of coin;add item at position where it should be;conbine the below'''h=self._coin()while h >= len(self._table):self.append_chain() # if the level is lower than h ,append itindex,temp=self.search_before(k,h)# (chain index , positions) chain=self._table[index]if chain.after(temp)._key==k:# if k in the table,change itreturn self.change(k,v)c_temp=self._Chain._Item(k,v,None,None)# current itemb_temp=self._Chain._Item(k,v,None,None)# below item self._size+=1 # size +1 for i in range(index,-1,-1): # trave the level from level index to 0chain.add_after(temp,c_temp) c_temp._below=b_temp # conbine the belowc_temp=b_temp# exchange itemb_temp=self._Chain._Item(k,v,None,None)if i==0:# end of the chainreturntemp=chain.below(temp)# change the below chainchain=self._table[i-1]#print(chain.after(temp) is chain.tail(),chain.after(temp)._key, chain.tail()._key)while chain.after(temp) is not chain.tail() and chain.after(temp)<k:temp=chain.after(temp) # chagne the tempdef change(self,k,v):''' delete and insert'''self.delete(k)self[k]=vdef delete(self,k):''' delete k or raise error'''index,temp=self.search_before(k)# find the item front kif self._table[index].after(temp)._key!=k:raise ValueError('none item')chain=self._table[index]for i in range(index,-1,-1): # trave the level from level index to 0del_item=chain.del_after(temp)# cut the after linkdel_item._below=None# cut the below linkif i ==0:# end of the chainreturntemp=chain.below(temp)chain=self._table[i-1]while chain.after(temp)!=k: # fand the new temptemp=chain.after(temp)def text62(n=10000):l1,l2=text61_getlist(n)# if there are too many node, python will breakt1=text61_time(l1,SkipTable())print('skiptable:',t1)text61() # 使用11.61的函数t2=text61_time(l2,SkipTable())print('skiptable:',t2)#text11.62:#text62()#11.63#node带有四个指针,分别指向父节点,前节点,后节点,孩子节点#_parent # | # _before - node - _after# |#_child# |# 4-node# / | | \# AB CD (A,B,C,D为别为各自链表的头节点)#如上图,一个4-node节点由三个node组成 其中第一个node的前节点指向A、孩子节点指向B;# 第二个node的前节点指向第一个节点、孩子节点指向C;# 第三个node的前节点指向第二个节点、孩子节点指向Dclass TreeMap2_3_4:BLANK=object() # in down_split method, substitute other nodeclass Position:''' position class'''def __init__(self,node,container):self._node=nodeself._container=containerdef element(self):''' return value of position '''return self._node._valuedef key(self):return self._node._keydef __eq__(self,other):return type(self)==type(other) and self._node is other._node#class _Node:''' creat the link node,'''def __init__(self,k,v,before=None,after=None,parent=None,child=None):self._key=kself._value=vself._before=beforeself._after=afterself._parent=parentself._child=child#--------------------------convennient the node------------------------ def __eq__(self,k):''' return true, if k==self._key'''if type(k) ==int:return self._key==kelif isinstance(k,type(self)):return self._key==k._keydef __nq__(self,k):return not self==kdef __lt__(self,k):''' return true if k < self._key'''if type(k) ==int:return self._key<kelif isinstance(k,type(self)):return self._key<k._keydef __gt__(self,k):return not self<k and self!=kdef __le__(self,k):return self<k or self == kdef __ge__(self, k):return self>k or self ==k#--------------------------------def __init__(self):''' root return the first node'''self._root=Noneself._size=0def _validate(self,p):''' Return associated node, if position is valid.'''if not isinstance(p, self.Position):raise TypeError('p must be proper Position type')if p._container is not self:raise ValueError('p does not belong to this container')if p._node._parent is p._node:# convention for deprecated nodesraise ValueError('p is no longer valid')return p._nodedef _make_position(self,node):''' return position of node '''return self.Position(node,self) if node != None else Nonedef _add_after(self,p,temp,head_node=None):''' add a node after p,p is Position class;reconect node's after,before parent,without child.'''node=self._validate(p)# temp's before is node,after is node's after#,parent is node's parenttemp._before=nodetemp._after=node._aftertemp._parent=node._parentnode._after = tempif temp._after is not None:temp._after._before=tempif head_node is not None:while temp is not None: # repoint child's parent，_add_beofre method can't repointsubnode = temp._childwhile subnode is not None:subnode._parent = head_nodesubnode = subnode._aftertemp = temp._afterreturn self._make_position(temp)def _add_before(self,p,temp,head_node=None):''' this method can only be used for p which before node is none;add a node before p,p is Position and head node;temp is a _Node;head_node is _Node class;reconnect node's child,parent'before and after.'''node=self._validate(p)# temp's before is node._before,after is node,#parent is node._parentif temp._before is not None and temp._child is None: # in case 2.1 of down_split methodtemp._child=node._beforeelse:temp._before=node._beforetemp._after=nodetemp._parent=node._parentnode._before=tempparent=self.parent(p)if parent is None:self._root=tempelse:parent=self._validate(parent)if parent._before is node:parent._before = tempif parent._child is node:parent._child = temptempnode=tempif head_node is not None:while tempnode is not None: # repoint child's parent，subnode = tempnode._childwhile subnode is not None:subnode._parent = head_nodesubnode = subnode._aftertempnode = tempnode._afterreturn self._make_position(temp) # now temp is the headdef _add(self,p,k,v,head):''' add a node in a proper posiiton '''node=self._validate(p)temp=self._Node(k,v)self._size+=1if node < k:self._add_after(p,temp)self._up_split(head)else:self._up_split(self._add_before(p,temp,temp))def _search(self,k,head=None,node=None):''' return the proper Position and head if chain's child is None;find begin of root if node is Nonehead and node are _Node class'''if node is None:node=self._roothead=node#print(node,k,self._root)if node>k: # recursion to node's beforeif node._before is None:# break the cursion if there is none childreturn self._make_position(node),self._make_position(head)return self._search(k,node._before,node._before)if node==k: # break the cursionreturn self._make_position(node),self._make_position(head)if node<k: # recursion to node's afterif node._after is not None:# if there is item after nodeif k<node._after: # node<k<node._afterif node._child is None: # node is the last nodereturn self._make_position(node),self._make_position(head)return self._search(k,node._child,node._child)else: # noke._after <kreturn self._search(k,head,node._after)else:if node._child is None:# if node is last Positionreturn self._make_position(node),self._make_position(head)return self._search(k,node._child,node._child)def _up_split(self,head):''' head is a Position class''' if self.is_filled(head):node=self._validate(head)mid=node._after._after # split in to tree parts, (node,mid,p2)p2=mid._after # p2 is the mid's child parent=node._parent# combine the tree partsnode._after._after=Nonep2._before=mid._childmid._child=p2p2._parent = parent# if parent is None , p2._parent is midtemp=p2._beforewhile temp is not None:# p2 became a head node ,repoint child and child._aftertemp._parent=p2temp=temp._aftertemp=p2._childwhile temp is not None:temp._parent = p2temp=temp._after# find the proper position for midif parent is not None: # if node isn't rootparent=self._validate(self.parent(self._make_position(node)))# get the parent nodeif parent>mid:if parent._before is node:# if mid add to the head ,the node and p2 's parent should be midself._add_before(self._make_position(parent),mid,mid)node._parent=midnode._after._parent=midreturn self._up_split(self._make_position(mid))mid._before=parent._beforemid._before._after=midmid._after=parentparent._before=midmid._parent=parent._parent if parent<mid:self._add_after(self._make_position(parent),mid)return self._up_split(self._make_position(node._parent))# Prevent overflow from passing upwardselse: # if node is root# make mid is the rootself._root=midmid._before=nodemid._after=Nonemid._parent=None# the node and p2 's parent should be midnode._parent=midnode._after._parent=midp2._parent=middef _pop(self,p,head):# warrring pop need to be devided in to situations''' cut all links related p;p is the Position;p._before will be p._after._before and the p._child need to be None'''node=self._validate(p)after=node._afterif after is not None:before=node._beforeself._pointer_repoint(self._make_position(node._after),p,head)after._before=before # repoint node's after node, node._after._before nodeelse:self._pointer_repoint(None,p,head)return self._make_position(node)def _replace(self,p,position,head):''' substitue position for p and return position '''node=self._validate(p)p_node=self._validate(position)if p_node._parent is not node:node._parent=p_node._parentnode._child=p_node._childnode._before=p_node._beforenode._after=p_node._afterself._pointer_repoint(p,position,head)return positiondef _pointer_repoint(self,p,position,head):''' the pointer to position repoints p ；when p is root and p.after is not empty,let p.after be root'''if p is not None: # in case p is None,when _pop() methodnode=self._validate(p)else:node = Nonep_node=self._validate(position)if p_node is self._root:# if position is root nodeself._root=nodeif position == head: # repoint node's child and parentparent=self._validate(self.parent(position)) if p_node._parent is not None else None# all of child repoint to nodetemp = p_node._before # before fractionwhile temp is not None:temp._parent = nodetemp = temp._aftertemp_node = p_node# child fractionwhile temp_node is not None:temp = temp_node._childwhile temp is not None:temp._parent = nodetemp = temp._aftertemp_node = temp_node._afterif parent is not None:# repoint parent's childif parent._before is p_node:parent._before=nodeelse:parent._child=nodeelse:# if node is not headp_node._before._after=nodeif p_node._after is not None:# repoint node's after node, node._after._before nodep_node._after._before =nodep_node._parent=Nonep_node._after=Nonep_node._before=Nonep_node._child=Nonedef _brother(self,p,r=True):''' return p's brother node;if r is Flase,denote the method working for recursion；'''node=self._validate(p)parent=self._validate(self.parent(p))parent_h=node._parentif parent._before is node:# get brotherbrother=parent._childbrother_head=brotherelse:brother1=parent._before if parent is parent_h else parent._before._childbrother_head =brother1while brother1._after is not None:brother1=brother1._afterif r:brother2=parent._after._child if parent._after is not None else Noneif not self.is_singular(self._make_position(brother2)) and self.is_singular(self._make_position(brother_head)):# let len less node be brotherbrother = brother2brother_head=brother2else:brother=brother1else:brother=brother1return self._make_position(brother),self._make_position(brother_head)def _down_split(self,position,r=True):''' cut chain of position ;case 1 :position's brother is not singularcase 2 :position's brother is singularcase 2.1 :position's parent is singular (this way need recursion)case 2.2 :position's parnet is not singual'''node = self._validate(position)parent=self._validate(self.parent(position))parent_h=node._parent # parent_h is parent's headbrother,brother_head=self._brother(position,r)brother=self._validate(brother)if not self.is_singular(brother_head) and r: # case 1brother_parent=self.parent(brother_head)temp1=self._pop(self._make_position(brother),brother_head)# replace temp1 with parentif node>brother: # there are different parents when different size relationship of brother and nodetemp2=self._replace(temp1,self._make_position(parent),self._make_position(parent_h))else:temp2 = self._replace(temp1, brother_parent, self._make_position(parent_h))# replace temp2 with positiontemp3=self._replace(temp2,position,position)return temp3else: # if brother is singular,case 2if self.is_singular(self._make_position(parent_h)): # case 2.1blank_node=self._Node(parent._key,TreeMap2_3_4.BLANK)blank=self._make_position(blank_node)temp1=self._replace(blank,self._make_position(parent),self._make_position(parent)) # replace parent Positionself._replace(temp1,position,position) # replace position with parentif brother>parent:blank_node._before = Noneself._add_before(self._make_position(brother),parent,parent)brother_head = self._make_position(parent)if blank_node<blank_node._parent:# Deal with the before and child value issues of blank nodesblank_node._before,blank_node._child=blank_node._child,blank_node._beforeelse:blank_node._child=Noneself._add_after(self._make_position(brother),parent,self._validate(brother_head))if blank_node>blank_node._parent:# Deal with the before and child value issues of blank nodesblank_node._before, blank_node._child = blank_node._child, blank_node._beforeif blank_node._parent is None: # if blank is rootblank_node._before=blank_node._child if blank_node._child is not None else blank_node._before # incase pop the nodeblank_node._child=Noneself._pop(blank,blank)self._root=self._validate(brother_head) if self._validate(brother_head)<parent else parentreturn self.root()# in case node is filledif self.is_filled(brother_head):blank_node._before, blank_node._child = blank_node._child, blank_node._beforeself._up_split(brother_head)if parent<brother and blank_node._before is None:# let new node be the _before of blank_nodeblank_node._before=blank_node._childblank_head=blank if blank_node<brother else self._make_position(blank_node._before)self._pop(blank,blank_head)returnreturn self._down_split(blank,False)else: # if parent is not sigular ,case 2.2TEMP=self._make_position(self._Node(TreeMap2_3_4.BLANK,TreeMap2_3_4.BLANK)) # TEMP uesed to repalce parent nodeself._replace(TEMP,self._make_position(parent),self._make_position(parent_h)) # parent Positionres=self._replace(self._make_position(parent),position,position)# position Positionif brother > parent: # add the older parent to brotherself._add_before(self._make_position(brother),parent,parent)brother_head=self._make_position(parent)else:self._add_after(self._make_position(brother),parent,self._validate(brother_head))if parent_h is parent: # delete tempif parent<brother: # let new node be the left node of TEMPTEMP._node._before=TEMP._node._child # for _pop mtehodTEMP._node._child=None# let parent._before be parent._after._before for the pop methodparent_h=TEMPelse:parent_h=self._make_position(parent_h)self._pop(TEMP,parent_h)self._up_split(brother_head)return self._make_position(res)def _subnode(self,p,head):''' find the subnode which should lt p of p '''node = self._validate(p)if p == head:temp=node._beforeelse:temp=node._before._childhead=tempif temp is not None:while temp._after is not None or temp._child is not None:while temp._after is not None:temp = temp._afterif temp._child is not None:temp=temp._childhead=tempreturn self._make_position(temp),self._make_position(head)else:return None,Nonedef _before(self,p,head):''' p is position ,head is p's head and a position;return position and head,position less than p '''node=self._validate(p) # find a proper subtree to searchif node._before is None: # node is leaf nodeif node._parent is None:# if p is the root nodereturn None,Nonehead=node._parenttemp=self._validate(self.parent(p))while temp._before is node: # looking up to the top, find the before the nodenode=temphead=temp._parenttemp=self._validate(self.parent(self._make_position(temp)))if temp is None: # if p is the leftmost nodereturn None,Noneif temp._before is not node:return self._make_position(temp),self._make_position(head)else:temp=node._before # temp is the target nodeif p == head : # if p is not head nodereturn self._search(node._key, temp, temp)elif temp._child is not None:temp=temp._childreturn self._search(node._key, temp, temp)else:return self._make_position(temp),headdef _next(self,p,head):''' p is position ,head is p's head and head is positionreturn position and head,position great than p'''node=self._validate(p)if node._child is not None:return self._search(node._key,node._child,node._child)if node._after is not None:return self._make_position(node._after),headtemp=self._validate(self.parent(head))# parent's child or before node is headhead=self._make_position(node._parent)# get the parent 's headwhile temp<=node: # lookup the parent's nodeif temp._after is not None: # if the parent has after node to return it, else travel to the top of the treereturn self._make_position(temp._after),headhead,temp=self._make_position(temp._parent),self._validate(self.parent(head))return self._make_position(temp), headdef _generate(self,p,head):''' recuisively yield _Node;n,head are class _Node;if return whole tree,p and head should convey both self._root.'''if p is None:returnif p is head:for i in self._generate(p._before,p._before):yield iyield self._make_position(p)for i in self._generate(p._child,p._child):yield ifor i in self._generate(p._after,head):yield idef _get_head(self,n):''' n is a Position, returning a node that is a Position '''n=self._validate(n)if n._child is not None:return self._make_position(n._child._parent)else:while n._before is not None:n=n._beforereturn self._make_position(n)def __len__(self):return self._sizedef __setitem__(self,k,v):if len(self)==0:self._root=self._Node(k,v)self._size+=1returnnode,head=self._search(k) # get the position and headif node.key()==k:node._node._value=velse:self._add(node,k,v,head)def __delitem__(self,k):position,head=self._search(k) # delete nodeself._size-=1if position.key() !=k:raise KeyError('key warring')subs,subs_head=self._subnode(position,head)if subs is not None:# dispose the positionif self.is_singular(subs_head):self._down_split(subs)if self._validate(position)._parent is not None: # in case head is changed,research positiont,head=self._search(position.element(),self._validate(position)._parent,self._validate(position)._parent)else :t,head=position, self.root()else:self._pop(subs,subs_head)return self._replace(subs, position, head)else:if self.root()==position: # if tree only has root nodeself._pop(position,position)self._size=0returnelse:if self.is_singular(head): # if position is a leaf node , a headreturn self._down_split(position)else:return self._pop(position,head)def __getitem__(self, k):''' return value of Position which key ==k,raise KeyError if k not find'''p,head=self._search(k)if p.key()==k:return p.element()else:raise KeyError('invalid key')def __contains__(self, k):p,head=self._search(k)if p.key()==k:return Trueelse:return Falsedef __iter__(self):for i in self._generate(self._root,self._root):yield i.element()def get(self, k, d):''' if k is found return k.element else return d'''p,head=self._search(k)return p.element() if p.key()==k else ddef is_filled(self,head):''' return True, If the head is connected to two nodes'''head=self._validate(head)n=1while head._after is not None:head=head._aftern+=1return n==4 # 4 is the maxinumdef is_singular(self,head):if head is None:return True node=self._validate(head)return node._after is Nonedef root(self):return self._make_position(self._root)def parent(self,p):''' find p's parent position;p have to be a head node.'''node=self._validate(p)parent=node._parentif parent is None:return Nonewhile not ( parent._before is node or parent._child is node): # mayparent=parent._after return self._make_position(parent)def items(self):return [(i.key(),i.element()) for i in self._generate(self._root,self._root)]def pop(self,k,d=None):if d is None:raise KeyError('d have be not None')try:self.__delitem__(k)except KeyError:return ddef popitem(self):import randomseed=random.randint(0,len(self)) for i in self._generate(self._root,self._root):if seed == 0:break seed-=1self.__delitem__(i.key())return (i.key(),i.element())def setdefault(self,k,d):if len(self)==0:self._root=self._Node(k,d)self._size+=1returnnode,head=self._search(k) # get the position and headif node.key()==k:return node.element()else:self._add(node,k,d,head)# 11.64def find_min(self):''' return first node of _generate'''temp=next(self._generate(self._root,self._root))return temp.key(),temp.element()def find_max(self):''' find the last and rightmost node'''temp=self._rootwhile temp._after is not None:temp=temp._afterwhile temp._child is not None:temp=temp._childwhile temp._after is not None:temp=temp._afterreturn temp._key,temp._valuedef find_lt(self,k):p,h=self._search(k)if p.key()==k:p,h=self._before(p,h)return p.key(),p.element()def find_le(self,k):p,h=self._search(k)return p.key(),p.element()def find_gt(self,k):p,h=self._search(k)p,h=self._next(p,h)return p.key(),p.element()def find_ge(self,k):p,h=self._search(k)if p.key()!=k:p,h=self._next(p,h)return p.key(),p.element()def find_range(self,start,stop=None):''' start and stop is key '''if stop==None:stop=startstart=self.first().key() # define the initial number of startif stop < start or stop>len(self):raise IndexError('parameter is invalid')nex,h=self._search(start) # find the first nodewhile 1: # get the next node in cyclesyield nex.element()if nex.key()< stop-1:nex,h=self._next(nex,h)else:breakdef reversed(self):''' return k all of the tree that reversed iter '''walk=self.last()head=self._get_head(walk)yield walk.element()for i in range(len(self)-1):walk,head=self._before(walk,head)yield walk.element()def first(self):''' finding the mininum node ,return it's Position'''walk=self._rootwhile walk._before is not None:walk=walk._beforereturn self._make_position(walk)def last(self):''' finding the maxnium node ,return it's Position'''walk=self._rootwhile 1: # find the node which is the max k.while walk._after is not None:walk=walk._afterif walk._child is not None:walk=walk._childhead=walkelse:breakreturn self._make_position(walk)def before(self,p):''' p is a Position,return a Position'''head=self._get_head(p)po,he=self._before(p,head)return podef after(self,p):''' p is a Position, return a Position'''head=self._get_head(p)po,he=self._next(p,head)return podef find_position(self,k):''' if k in the tree return a Position that belong k, else raise Error'''p,h=self._search(k)if p.key()==k:return pelse:raise KeyError('invalid key')def text63(o=100):t = TreeMap2_3_4()#----------------del testfor i in range(o):t[i]=str(i)+'#'for i in range(o):del t[i]print('order done')for i in range(o):t[i]=str(i)+'#'for i in range(o-1,-1,-1):# print(i)del t[i]print('reverse order done')#------------ test del from the midstfor i in range(o):t[i]=str(i)+'#'for i in range(o//2,-1,-1):# print(i)del t[i]print('midst previous done')for i in range(o//2+1,0):# print(i)del t[i]print('midst afterwards done')print(3 in t)print(t.get(-3,'d'))print(t.items())#del t#print(t)print(iter(t))print(t.pop(-3,'test pop'))print(t.popitem())print(t.setdefault(-3,'-3#'),t[-3])#text63(180)# 11.64 见11.63的类中def text64():t = TreeMap2_3_4()for i in range(1000):t[i]=str(i)+"#"print(t.find_min())print(t.find_max())print(t.find_lt(500))print(t.find_le(500))print(t.find_gt(500)) print(t.find_ge(500))for i in t.find_range(1000):print(i)for i in t.reversed():print(i)#text64()# 11.65 见11.53的类中def text65():t=TreeMap2_3_4()for i in range(1000):t[i]=str(i)+'#'a=t.first()b=t.last()print(a.element(),t.after(a).element())print(b.element(),t.before(b).element())print(t.find_position(999).element())print(t.find_position(333).element())#text65()#11.66 使用习题11.63实现的234树和源代码中的红黑树from TheCode.ch11.red_black_tree import RedBlackTreeMap as RBTfrom TreeMap2_3_4 import TreeMap2_3_4 as TM2from queue import Queueclass Convert(RBT,TM2):''' convert RedBlackTree to 234TreeMap or covert 234TreeMap to RedblackTree '''def __init__(self):if 'y'==input('define 2-3-4Tree pressing y else pressing others'):self._tree=TM2()self._arm=RBT()else:self._tree=RBT()self._arm=TM2()self._rbt=Queue()self._tm=Queue()def __getitem__(self,k):return self._tree[k]def __setitem__(self,k,v):self._tree[k]=[v]def _convertRBT(self,chain):''' convent 2_3_4tree's node to RedBlackTree;return black nodechain is a _Node of TM2;there are 3 kind of case;case1 there are 3 node,;case2 there are 2 node;case 1 there is 1 node.'''first=RBT._Node(RBT._Item(chain._key,chain._value))second=RBT._Node(RBT._Item(chain._after._key,chain._after._value)) if chain._after is not None else Nonethird=RBT._Node(RBT._Item(chain._after._after._key,chain._after._after._value)) if (chain._after is not None and chain._after._after is not None)else Noneif self._rbt.empty():self._arm._root=second if second is not None else firstif second is not None: # case there are 2 or 3 number of nodesecond._red = False # set second blackself._combine(second,first,False)self._rbt.put((first,'l')) # case 1:input queueself._rbt.put((first,'r'))if third is not None:self._combine(second,third)self._rbt.put((third,'l'))# case 2:input queueself._rbt.put((third,'r'))return secondelse:self._rbt.put((second,'r'))return secondelse:first._red =False # set first blackself._rbt.put((first,'l')) # case 3:input queueself._rbt.put((first,'r'))return firstdef _combine(self,parent,child,right=True):''' combine parent and right child if right is True,else combine parent and left child ;parent and child is _Node of RedBlackTreeMap.'''if right:parent._right=childelse:parent._left=childchild._parent=parentdef _circleRBT(self):''' control 234TreeMAp converning to RBT '''if self._tm.empty():returnwalk=self._tm.get()res = self._convertRBT(walk)if walk._before is not None: # if walk is leaf node returnself._tm.put(walk._before)# else put child to self._tmwhile walk is not None: self._tm.put(walk._child)walk=walk._afterblack=resif black==self._arm._root:return # Don't conbine the walk when first allocate the methodinfo=self._rbt.get()if info[1]=='r':self._combine(info[0],black)else:self._combine(info[0],black,False)def _convertTM(self,black):''' convert node of RedBlackTree to 234TM node;put position to _tm'''second=TM2._Node(black._element._key,black._element._value)first=TM2._Node(black._left._element._key,black._left._element._value) if (black._left is not None and black._left._red) is True else Nonethird=TM2._Node(black._right._element._key,black._right._element._value) if (black._right is not None and black._right._red)is True else Nonesecond._before=firstsecond._after=thirdif self._tm.empty():# set root nodeself._arm._root=first if first is not None else secondhead=secondif first is not None:head=firstfirst._after=secondself._tm.put((first,False,head)) # put (first,judge) to _tm, if the judge is Ture meaning _before nodeself._tm.put((first,True,head))else:self._tm.put((second,False,head))if third is not None:third._before=secondself._tm.put((third,False,head))self._tm.put((third,True,head))else:self._tm.put((second,True,head))return headdef _combineTM(self,parent,head,child,right):''' In a 234Tm,conbine child to its parent's child,if parameter right is True '''if right:parent._child=childelse:if head is not parent: # case in 2node or 3nodeparent._before._child=childelse: # case in 1nodeparent._before=childwhile child is not None: # repoint to parentchild._parent=headchild=child._afterdef _circleTM(self):walk=self._rbt.get()res = self._convertTM(walk)if walk._left is not None :if walk._left._red is True: # if walk._left is redif walk._left._left is not None: self._rbt.put(walk._left._left)# this node have to be a blackself._rbt.put(walk._left._right)else:self._rbt.put(walk._left)if walk._right is not None:if walk._right._red is True:if walk._right._left is not None:self._rbt.put(walk._right._left)self._rbt.put(walk._right._right)else:self._rbt.put(walk._right)parent=resif parent==self._arm._root:return # Don't conbine the walk when first allocate the methodinfo=self._tm.get()self._combineTM(info[0],info[2],parent,info[1])def changeTM(self):''' convert RBT to 234TM '''if len(self._tree)==0:raise ValueError('There is no item.')self._rbt.put(self._tree._root)while not self._rbt.empty():self._circleTM()self._arm._size=self._tree._size # set size of armdef arm(self):return self._armdef changeRBT(self):''' convert 234 tree to RBT'''if len(self._tree)==0:raise ValueError('There is no item.')self._tm.put(self._tree._root)while not self._tm.empty() :self._circleRBT()self._arm._size=self._tree._size # set size of arm# 测试234转红黑树# t=Convert()# for i in range(100):# t[i]=str(i)# t.changeRBT()# a=[i for i in t.arm().__iter__()]# for i in range(100):# text if equal#if i not in a:# print(i,'*')# 测试红黑树转234树#t = Convert()#for i in range(100):# t[i]=str(i)#t.changeTM()#a=[i for i in t.arm().__iter__()]#print(a)# 11.67 根据10-17代码所示，只需更改_MapType即可更改映射from TheCode.ch10.multi_map import MultiMapfrom TheCode.ch11.avl_tree import AVLTreeMapclass MultiMap67(MultiMap):_MapType=AVLTreeMapdef text67():t=MultiMap67()for i in range(10):t.add(i,str(i)+'#')print([i for i in t])#text67()# 11.68from TheCode.ch11.splay_tree import SplayTreeMapclass STM(SplayTreeMap):''' rewrite _subtree_search method '''def _subtree_search(self,p,k):''' find the z,y,x then rotate them '''z=pwhile True:y=self.left(z) if z.element()._key>k else self.right(z)if y is None:# can't find kreturn zif y.element()._key>k and z.element()._key>k: x=self.left(y)if x==None: self._rotate(y)# zig else: # zig-zigself._rotate(y)self._rotate(x)elif y.element()._key<k and z.element()._key<k:x=self.right(y)if x==None:self._rotate(y)# zigelse:self._rotate(y)# zig-zigself._rotate(x)else: # zig-zagif x==None:self._rotate(y)# zigelse:self._ratate(x)# zig-zagself._ratate(x)if x is not None: # control circle if x.element()._key==k:return xz=xelse:z=ydef _rebalance_insert(self,p):passdef _rebalance_access(self,p):pass#11.68 时间复杂度比标准的少lgn# t=STM()# for i in range(100):#t[i]=str(i)+'#'# print([i for i in t])#11.69 在优先级队列中使用添加avl平衡因子,让其在merge后的add操作尽可能高效率class Heap:''' A heap that find the min '''class _Node:class _Item:def __init__(self,key,value):self._key=keyself._value=valuedef __eq__(self,k):return self._key==k._keydef __gt__(self,k):return self._key>k._keydef __lt__(self,k):return self._key<k._keydef __init__(self,k,v,parent=None):self._parent=parentself._left=Noneself._right=Noneself._factor=0 # if _factor is 1, preform left deeper than rightself._element=self._Item(k,v)def __eq__(self,k):return self._element==k._elementdef __gt__(self,k):return self._element>k._elementdef __lt__(self,k):return self._element<k._elementdef __init__(self):self._root=Noneself._size=0def _min(self,n1,n2):''' n1,n2 are self._Node '''if n1 is None:return n2if n2 is None:return n1return n1 if n1<n2 else n2def _replace(self,n1,n2):''' replace n1._element with n2._element'''n1._element,n2._element=n2._element,n1._elementdef _down(self,k):''' After del method,be used for finding a porper position'''while True:child=self._min(k._left,k._right)if (child is not None)and k>child:self._replace(k,child)k=childelse:returndef _up(self,k):''' After add method ,be used for find a porper position'''while True:if k._parent is not None and k<k._parent:self._replace(k,k._parent)k=k._parentelse:returndef _pop(self,walk):''' pop a node that is the k's leaf that is smaller than brother;return the node and the hight;k is a self._Node.'''h=-1while True: # find a walk that is the leafh+=1if walk._factor>0:walk=walk._leftelse:if walk._right is not None:walk=walk._rightelse:# now walk._right and walk._left is Nonebreakif walk is not self._root:if walk._parent._factor!=0:# recalculate the factor if walk's height be changetemp=walkwhile temp._parent is not None:if self.is_left(temp):temp._parent._factor-=1else:temp._parent._factor+=1if temp._parent._factor==0:# when parent._factor equal zero stop spreadingtemp=temp._parentelse:breakelse:if self.is_left(walk):walk._parent._factor-=1else:walk._parent._factor+=1if (walk._parent._left is not None) and walk._parent._left is walk: # cut down chainwalk._parent._left=Noneelse:walk._parent._right=Nonewalk._parent=Noneelse:# if there is only one node in Heapself._root=Noneself._size -= 1return walk,hdef is_left(self,p):return (p is p._parent._left) if p._parent is not None else Falsedef is_right(self,p):return (p is p._parent._right) if p._parent is not None else False def remove_min(self):''' favorite is right'''res=self._root._elementwalk=self._pop(self._root)[0]if self._root is not None:self._replace(walk, self._root)self._down(self._root)return res._key,res._valuedef min(self):return self._root._element._valuedef add(self,k,v):''' favorite is left '''self._size += 1if self._root is None:self._root=self._Node(k,v)else:walk=self._rootwhile True: # find the leaf and contorl the factorif walk._factor>0:if walk._right is not None:walk=walk._rightelse:walk._right=self._Node(k,v,walk) # add a new _Nodewalk=walk._rightbreakelse:if walk._left is not None:walk=walk._leftelse:walk._left=self._Node(k,v,walk) # add a new _Nodewalk=walk._leftbreakif walk._parent._factor==0: # recalculate the factor if walk's height be changedtemp=walkwhile temp._parent is not None:if self.is_left(temp):temp._parent._factor+=1else:temp._parent._factor-=1if temp._parent._factor !=0: # when parent._factor==0 stop spreading.temp=temp._parentelse:breakelse:if self.is_left(walk):walk._parent._factor+=1else:walk._parent._factor-=1self._up(walk) # handle the new Nodedef root(self):return self._rootdef merge(self,h):if not type(self)==type(h):raise KeyError('parameter is not isinstance whit Heap')last,h1=self._pop(self._root)walk=h.root()h2=1while walk._left is not None: # caculate the hight of hif walk._factor<0:walk=walk._rightelse:walk=walk._lefth2+=1last._factor=h1-h2last._left=self._root # chain these Heaplast._right=h.root()self._root._parent=lasth.root()._parent=lasth._root=None# handle the field of self and hself._size+=h._sizeh._size=0self._root=lastself._down(self._root)# text11.69# t=Heap()# for i in range(10):#t.add(i,i)# print(t.min())# for i in range(10):#print(t.remove_min())# for i in range(20,40):#t.add(i,i)# l=Heap()# for i in range(100):#l.add(i,i)# t.merge(l)# print(t.min())# for i in range(10):#print(t.remove_min())# for i in range(10):#print(t.remove_min())# for i in range(100):#print(t.remove_min())# 11.70 引用源代码中的avl树from TheCode.ch11.avl_tree import AVLTreeMapimport randomclass SkipFraiy:''' ''' def __init__(self,n):self._tree= AVLTreeMap()self._list=[]self._n=nself._store=[] # store empty indexfor i in range(n):self._list.append(self._add(i,1000000))def _add(self,k,v):"""Assign value v to key k, overwriting existing value if present."""if self._tree.is_empty():leaf = self._tree._add_root(self._tree._Item(k, v))# from LinkedBinaryTreeelse:p = self._tree._subtree_search(self._tree.root(), k)if p.key() == k:return self._add(k+round(random.uniform(-1,1),2),v)else:item = self._tree._Item(k, v)if p.key() < k:# inherited from LinkedBinaryTreeleaf = self._tree._add_right(p, item)else:# inherited from LinkedBinaryTreeleaf = self._tree._add_left(p, item)# hook for balanced tree subclassesself._tree._rebalance_insert(leaf)return leafdef after(self,p):''' return the next node after p '''return self._tree.after(p)def before(self,p):''' return the next node after p '''return self._tree.before(p)def delete(self,p):self._tree.delete(p)def run(self):for i in range(self._n):temp=self._list[i]if temp is None:continueif temp._node._parent is temp._node: # if temp was deleted ,add index to self._storeself._list[i]=Noneself._store.append(i)continueaim=self.before(temp)aim2=self.after(temp)if aim is None :aim=aim2elif aim2 is not None:aim=aim if temp.key()-aim.key()<aim2.key()-temp.key() else aim2# find the closer nodeaim.element()._value/=2gold=aim.element()._value+temp.element()._value # calculate the key and nodekey=temp.key()+round(random.uniform(-1,1),2)*goldself.delete(temp)if len(self._store)==0:self._list.append(self._add(key,gold))else:self._list[self._store.pop()]=self._add(key,gold)def print(self):for i in self._list:if i is not None:print('The node of key equal',i.key(),'value is',i.value())#text11.70# t=SkipFraiy(30)# for i in range(10):#t.run()# t.print()