AVL树

群组
欢迎加入群组,闲聊工作&技术&问题等

AVL树定义

AVL树是一个带平衡条件的二叉搜索树.AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis,他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构.其主要满足以下性质:
1)左右子树高度差的绝对值不超过1;
2)左右子树也是AVL树.
之前我们已经了解到一颗具有n个节点二叉搜索树最大深度为n,最小深度为logn.二叉树的深度越小其搜索时间复杂度对应也就越小.一个深度为logn的二叉查找树其搜索算法的时间复杂度为logn.

平衡因子

AVL树是带有平衡条件二叉搜索树,其左右子树的高度差绝对值不超过1,这个平衡条件我们称为平衡因子(balance factor).

AVL树的构造

var root:BinaryTree<T>?

    // MARK: - 构造函数
    init() {

    }

查找

/// 查找操作
    ///
    /// - Parameters:
    ///   - binaryTreeNode: 根节点
    ///   - value: 待查找的值
    /// - Returns: 查找到的节点
    func find(binaryTreeNode:BinaryTree<T>?, value:T) -> BinaryTree<T>? {
        guard let node = binaryTreeNode else { return nil }
        if node.value == value {
            return node
        } else if value < node.value {
            return find(binaryTreeNode: node.leftChildNode, value: value)
        } else {
            return find(binaryTreeNode: node.rightChildNode, value: value)
        }
    }

旋转

对于一个非平衡的二叉搜索树,我们可以通过旋转的手段让其左右子树高度差不超过1从而达到平衡转变成一个AVL树.其中旋转的次数可能是1次或者多次.

左旋转

左旋转即向左旋转,逆时针旋转.

/// 左旋转
    ///
    /// - Parameter binaryTreeNode: 待旋转的节点
    /// - Returns: 旋转后的节点
    func leftRotate(binaryTreeNode:BinaryTree<T>?) -> BinaryTree<T>? {
        guard let pivot = binaryTreeNode?.rightChildNode else { return binaryTreeNode }
        binaryTreeNode?.rightChildNode = pivot.rightChildNode
        pivot.leftChildNode = binaryTreeNode
        binaryTreeNode?.height = max((binaryTreeNode?.leftHeight)!, (binaryTreeNode?.rightHeight)!) + 1
        pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
        return pivot
    }

右旋转

右旋转即向右旋转,顺时针旋转.

/// 右旋转
    ///
    /// - Parameter binaryTreeNode: 待旋转的节点
    /// - Returns: 旋转后的节点
    func rightRotate(binaryTreeNode:BinaryTree<T>?) -> BinaryTree<T>? {
        guard let pivot = binaryTreeNode?.rightChildNode else { return binaryTreeNode }
        binaryTreeNode?.leftChildNode = pivot.rightChildNode
        pivot.rightChildNode = binaryTreeNode
        binaryTreeNode?.height = max((binaryTreeNode?.leftHeight)!, (binaryTreeNode?.rightHeight)!) + 1
        pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
        return pivot
    }

左右旋转

/// 左右旋转
    ///
    /// - Parameter binaryTreeNode: 待旋转的节点
    /// - Returns: 选择后的节点
    func leftRightRotate(binaryTreeNode:BinaryTree<T>?) -> BinaryTree<T>? {
        guard let leftChild = binaryTreeNode?.leftChildNode else { return binaryTreeNode }
        binaryTreeNode?.leftChildNode = leftRotate(binaryTreeNode: leftChild)
        return rightRotate(binaryTreeNode: binaryTreeNode)
    }

右左旋转

/// 右左旋转
    ///
    /// - Parameter binaryTreeNode: 待旋转的节点
    /// - Returns: 旋转后的节点
    func rightLeftRotate(binaryTreeNode:BinaryTree<T>?) -> BinaryTree<T>? {
        guard let rightChild = binaryTreeNode?.rightChildNode else { return binaryTreeNode }
        binaryTreeNode?.rightChildNode = rightRotate(binaryTreeNode: rightChild)
        return leftRotate(binaryTreeNode: binaryTreeNode)
    }

插入

/// 插入操作
    ///
    /// - Parameter value: 待插入的值
    func insert(value:T) -> Void {
        root = insert(binaryTreeNode: root, value: value)
    }

    private func insert(binaryTreeNode:BinaryTree<T>?, value:T) -> BinaryTree<T>? {
        guard let node = binaryTreeNode else { return BinaryTree(value: value) }
        if value < node.value {
            node.leftChildNode = insert(binaryTreeNode: node.leftChildNode, value: value)
        } else {
            node.rightChildNode = insert(binaryTreeNode: node.rightChildNode, value: value)
        }
        let balanceNode = balance(binaryTreeNode: node)
        balanceNode.height = max(balanceNode.leftHeight, balanceNode.rightHeight) + 1
        return balanceNode
    }

删除

/// 删除操作
    ///
    /// - Parameter value: 待删除的值
    func delete(value:T) -> Void {
        root = delete(binaryTreeNode: root, value: value)
    }

    func delete(binaryTreeNode:BinaryTree<T>?, value:T) -> BinaryTree<T>? {
        guard let node = binaryTreeNode else { return nil }
        if node.value == value {
            if node.leftChildNode == nil && node.rightChildNode == nil {
                return nil
            }

            if node.leftChildNode == nil {
                return node.rightChildNode
            }

            if node.rightChildNode == nil {
                return node.leftChildNode
            }

            node.value = (node.rightChildNode?.minNode.value)!
            node.rightChildNode = delete(binaryTreeNode: node.rightChildNode, value: node.value)
        } else if value < node.value {
            node.leftChildNode = delete(binaryTreeNode: node.leftChildNode, value: value)
        } else {
            node.rightChildNode = delete(binaryTreeNode: node.rightChildNode, value: value)
        }
        let balanceNode = balance(binaryTreeNode: node)
        balanceNode.height = max(balanceNode.leftHeight, balanceNode.rightHeight) + 1
        return balanceNode
    }

源码地址

        这里的实现代码已放到GitHub,测试用例详见DataStructureAlgorithmTests.swift文件

参考文献

https://zh.wikipedia.org/wiki/AVL%E6%A0%91
《数据结构与算法分析C语言描述》(Data Structures and Algorithm Analysis in C:Second Edition)–译者: 冯舜玺


  转载请注明: waitwalker AVL树

 上一篇
堆
群组欢迎加入群组,闲聊工作&技术&问题等 堆是二叉树的一种,分为最小堆:其根节点恒小于子节点;最大堆:其根节点恒大于子节点.堆总是一颗完全二叉树,除了最底层,其它层都被填满,且最底层尽可能从左往右填入.常见的堆有二叉堆,斐
下一篇 
二叉搜索树 二叉搜索树
群组欢迎加入群组,闲聊工作&技术&问题等 二叉查找树定义二叉搜索树也叫二叉查找树(Binary Search Tree)是二叉树的一个类型.二叉搜索树具有以下性质:1)若任意节点的左子树不空,则左子树上所有节点的值均小于它
  目录