完美平衡
完美平衡的二叉搜索树是完全对称的，最底部的节点是完全充满的
AVL1.png
平衡二叉树
除了最底层的节点，每一个节点必须充满节点
屏幕快照 2020-06-17 下午11.41.31.png
实现
新建AVLNode，设置一个height属性，记录节点的高度，左节点的高度和右节点的高度差，最高需小于等于1。我们将左右节点的高度差差叫做 balance factor
public class AVLNode<Element> {
public var value: Element
public var leftChild: AVLNode?
public var rightChild: AVLNode?
public var height = 0
public init(value: Element) {
self.value = value
}
public var balanceFactor: Int {
return leftHeight - rightHeight
}
public var leftHeight: Int {
return leftChild?.height ?? -1
}
public var rightHeight: Int {
return rightChild?.height ?? -1
}
}
AVL4.png
这是一个平衡的二叉搜索树----除了最底层，所有的节点都填充满了节点，
- 蓝色的字代表节点的高度
- 绿色的字代表该节点的平衡因子
旋转
左旋转
一个左旋转的通用场景如以下所示：对节点X进行左旋转
AVL5.png
在左旋转前后，右两个需要知道的点：
- 中序遍历得到的结果一致
- 整个树的减少了一层
private func leftRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
// 右右
//将 node 的右子树 作为 枢纽，该节点将会成为node的右子树
let pivot = node.rightChild!
node.rightChild = pivot.leftChild
pivot.leftChild = node
node.height = max(node.leftHeight, node.rightHeight) + 1
pivot.height = max(node.leftHeight, node.rightHeight) + 1
return pivot
}
下图是对 25 进行左旋转前后的比较
AVL6.png
其中 25 与代码中
node相对应， 37 与 pivot 相对应左旋转就是 node成为其右子树的左子树
右旋转
右旋转是完全和左旋转相反的，如果是因为左子树造成的不平衡，就需要用右旋转来平衡
AVL7.png
private func rightRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
// 左左
// 将节点的左子树作为枢纽，该节点将成为node的左子树
let pivot = node.leftChild!
node.leftChild = pivot.rightChild
pivot.rightChild = node
node.height = max(node.leftHeight, node.rightHeight) + 1
pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
return pivot
}
右旋转：node成为其 左子树的右子树
右-左旋转
对于左旋转来讲，旋转的子节点全都在右边，我概括为 右右
对于右旋转来讲, 旋转的子节点全都在左边，我概括为 左左
但有的情况就不是这种全部在右边或者全部在左边了，如下图所示：
AVL8.png
先对 37 进行 右旋转，然后对 25 进行左旋转
AVL9.png
private func rightLeftRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
// 左右
guard let rightChild = node.rightChild else {
return node
}
node.rightChild = rightRotate(rightChild)
return leftRotate(node)
}
左-右旋转
AVL10.png
- 对 10 进行左旋转（节点10 成为其右子树的左子树）
- 对 25 进行右旋转 (节点25 成为其左子树的右子树)
private func leftRightRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
guard let leftChild = node.leftChild else {
return node
}
node.leftChild = leftRotate(leftChild)
return rightRotate(node)
}
平衡
我们通过平衡因子来判断是哪一种情况导致的不平衡,添加如下代码
private func balanced(_ node: AVLNode<Element>) -> AVLNode<Element> {
switch node.balanceFactor {
case 2:
// ...
case -2:
// ...
default:
return node
}
}
当balanceFactor == 2时，说明左边的树比较高，导致的不平衡，可以分为以下两种情况
AVL11.png
- 图1，节点10 的
balanceFactor == 2节点 5的balanceFactor == 1, 对 节点10 进行右旋转（将 节点 10 成为其左子树 5 的右子树） - 图2，节点10 的
balanceFactor == 2节点 5的balanceFactor == -1, 需要对 节点 5进行左旋转，（将节点 5成为其右节点7的左节点），旋转完成后，就变成了图1的情况
由此我们可以得出
private func balanced(_ node: AVLNode<Element>) -> AVLNode<Element> {
switch node.balanceFactor {
case 2:
// 左边高， 两种情况 ：1，左左。 2，左右
if let leftChild = node.leftChild, leftChild.balanceFactor == -1 {
// 左右
return leftRightRotate(node)
}else {
// 左左
return rightRotate(node)
}
case -2:
// 右边高，两种情况：1，右右。 2，右左
if let rightChild = node.rightChild, rightChild.balanceFactor == 1 {
//右左
return rightLeftRotate(node)
}else {
// 右右
return leftRotate(node)
}
default:
return node
}
}
每添加一个新节点，我们都需要对 二叉搜索树进行平衡
extension AVLTree {
private func insert(from node: AVLNode<Element>?, value: Element) -> AVLNode<Element> {
guard let node = node else {
return AVLNode(value: value)
}
if value < node.value {
node.leftChild = insert(from: node.leftChild, value: value)
} else {
node.rightChild = insert(from: node.rightChild, value: value)
}
let balancedNode = balanced(node)
balancedNode.height = max(balancedNode.leftHeight, balancedNode.rightHeight) + 1
return balancedNode
}
}
在删除节点时，我们也需要对节点进行平衡
private func remove(node: AVLNode<Element>?, value: Element) -> AVLNode<Element>? {
guard let node = node else {
return nil
}
if value == node.value {
if node.leftChild == nil && node.rightChild == nil {
return nil
}
if node.leftChild == nil {
return node.rightChild
}
if node.rightChild == nil {
return node.leftChild
}
node.value = node.rightChild!.min.value
node.rightChild = remove(node: node.rightChild, value: node.value)
} else if value < node.value {
node.leftChild = remove(node: node.leftChild, value: value)
} else {
node.rightChild = remove(node: node.rightChild, value: value)
}
let balancedNode = balanced(node)
balancedNode.height = max(balancedNode.leftHeight, balancedNode.rightHeight) + 1
return balancedNode
}
最后附上本文的相关代码DataAndAlgorim
网友评论