AVL树 | waitwalker

数据结构与算法

发布日期: 2019-04-30

文章字数: 959

阅读时长: 4 分

阅读次数:

群组
Flutter,iOS,Android,Python等,闲聊工作&技术&问题;
个人主页:https://waitwalker.cn
telegram群链接:https://t.me/joinchat/Ej0o0A1ntlq5ZFIMzzO5Pw

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
    }