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
"""

,

"""
newRoot = self
if val <= self.value:
if self.heightDifference() == 2:
if val <= self.left.value:
newRoot = self.rotateRight()
else:
newRoot = self.rotateLeftRight()
else:
if self.heightDifference() == -2:
if val > self.right.value:
newRoot = self.rotateLeft()
else:
newRoot = self.rotateRightLeft()
newRoot.computeHeight()
return newRoot
"""
val

parent

(

)

,

"""
if parent is None:
return BinaryNode(val)
122
5
return parent
5-13

parent
None
。这个尾递归能够确保新加入的元素永远是

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.