AVL树

2020-06-18 本文已影响0人 Bel李玉

完美平衡

完美平衡的二叉搜索树是完全对称的，最底部的节点是完全充满的

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

参考链接《Data Structures & Algorithms in Swift》

AVL树

完美平衡

平衡二叉树

实现

旋转

左旋转

右旋转

右-左旋转

左-右旋转

平衡

猜你喜欢

热点阅读