搜索算法
121
搜索算法
class BinaryNode:
def __init__(self, value=None):
"""
创建函数
"""
self.value = value
self.left = None
self.right = None
self.height = 0
def computeHeight(self):
"""
计算结点的高度
"""
height = -1
if self.left:
height = max(height, self.left.height)
if self.right:
height = max(height, self.right.height)
self.height = height + 1
def heightDifference(self):
"""
计算子
结点的高度差
"""
leftTarget = 0
rightTarget = 0
if self.left:
leftTarget = 1 + self.left.height
if self.right:
rightTarget = 1 + self.right.height
return leftTarget - rightTarget
def add(self, val):
"""
将一个
结点加入二叉搜索树中
,
并且在需要的时候再平衡
"""
newRoot = self
if val <= self.value:
self.left = self.addToSubTree(self.left, val)
if self.heightDifference() == 2:
if val <= self.left.value:
newRoot = self.rotateRight()
else:
newRoot = self.rotateLeftRight()
else:
self.right = self.addToSubTree(self.right, val)
if self.heightDifference() == -2:
if val > self.right.value:
newRoot = self.rotateLeft()
else:
newRoot = self.rotateRightLeft()
newRoot.computeHeight()
return newRoot
def addToSubTree(self, parent, val):
"""
val
加入以
parent
为根结点的子树中
(
如果存在
)
并且返回根结点
,
因为有可能发生旋转操作产生新的根结点
"""
if parent is None:
return BinaryNode(val)
122
5
parent = parent.add(val)
return parent
5-13
add
实现非常优雅:每次迭代的时候在两个递归函数之间选择一个调用。这个
方法递归式地遍历这棵树,有时走
子树有时走
子树,直到
addToSubTree
最终将一
结点加入空子树中(即
parent
None
。这个尾递归能够确保新加入的元素永远是
结点。当这个操作结束之后,
add
方法就需要决定是否需要进行旋转操作来满足
AV L
性质
。这些旋转操作从最接近叶结点的地方开始,一直向上到根结点为止。由于树本来
是平衡的,因此旋转的数目至多为
O
(log
n
)
次。由于每次旋转操作的步骤数都是固定的,
因此维护
AV L
性质
所需要的费用至多为
O
(log
n
)
。例
5-14
即右旋(
rotateRight
方法)
和右旋-左旋(
rotateRightLeft
方法)的实现。
5-14
rotateRight
rotateRightLeft
方法
def rotateRight(self):
"""
在给定结点上进行右旋操作
"""
newRoot = self.left
grandson = newRoot.right
self.left = grandson
newRoot.right = self
self.computeHeight()
return newRoot
def rotateRightLeft(self):
"""
在给定结点上先进行右旋
,
然后进行左旋操作
"""
child = self.right
newRoot = child.left
grand1 = newRoot.left
grand2 = newRoot.right
child.left = grand2
self.right = grand1
newRoot.left = self
newRoot.right = child
child.computeHeight()
self.computeHeight()
return newRoot
5-15
补充了整个旋转操作,即左旋
rotateLeft
方法)和左旋-右旋
rotateLeftRight
法)
5-15
rotateLeft
rotateLeftRight
方法
def rotateLeft(self):
"""
在给定结点上进行左旋操作
"""
newRoot = self.right
grandson = newRoot.left
搜索算法
123
搜索算法
self.right = grandson
newRoot.left = self
self.computeHeight()
return newRoot
def rotateLeftRight(self):
"""
在给定结点上先进行左旋
,
然后进行右旋操作
"""
child = self.left
newRoot = child.right
grand1 = newRoot.left
grand2 = newRoot.right
child.right = grand1
self.left = grand2
newRoot.left = child
newRoot.right = self
child.computeHeight()
self.computeHeight()
return newRoot
为了完全支持二叉搜索树的所有动态特性,我们还需要能够高效地删除元素。当从二叉
搜索树中删除元素时,维护
二叉搜索树的性质
非常重要。如果
目标
结点没有左子结点
我们可以简单地把其右子结点提升目标结点的位置上否则,就要找到左子树中
的值最大的结点,然后将其放在目标结点的位置上。这里有一个小性质:左子树的值最
大的结点必然没有右子结点,所以我们可以简单地把这个值最大的结点的左子树放在它
自己的位置上,然后将这个结点放入
目标
结点的位置,如图
5-14
所示。例
5-16
是该方
法的实现。
5-16
BinaryNode
remove
removeFromParent
方法
def removeFromParent(self, parent, val):
"""
删除操作的辅助方法,保证正确删除有子结点结点
"""
if parent:
return parent.remove(val)
return None
def remove(self, val):
"""
从二叉树中删除
val
,可以
结合删除方法使用
"""
newRoot = self
if val == self.value:
if self.left is None:
return self.right
child = self.left
while child.right:
child = child.right
124
5
childKey = child.value
self.left = self.removeFromParent(self.left, childKey)
self.value = childKey
if self.heightDifference() == -2:
if self.right.heightDifference() <= 0:
newRoot = self.rotateLeft()
else:
newRoot = self.rotateRightLeft()
elif val < self.value:
self.left = self.removeFromParent(self.left, val)
if self.heightDifference() == -2:
if self.right.heightDifference() <= 0:
newRoot = self.rotateLeft()
else:
newRoot = self.rotateRightLeft()
else:
self.right = self.removeFromParent(self.right, val)
if self.heightDifference() == 2:
if self.left.heightDifference() >= 0:
newRoot = self.rotateRight()
else:
newRoot = self.rotateLeftRight()
newRoot.computeHeight()
return newRoot
ځ෸أڦ঳ۅ
ፑጱຏዐڦ
ፌٷڦ঳ۅ
5-14:寻找左子树中的最大值

Get 算法技术手册(原书第2 版) now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.