目录

一、平衡二叉树

二、实现

三、小结

---

一、平衡二叉树

平衡二叉树也叫AVL树，它或者是一颗空树，或者具有以下性质的二叉排序树：它的左子树和左子树的高度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。

二、实现

package Algorithm.avl

public class AVLNode {
    public var key: Int64
    public var height: Int64
    public var left: Option<AVLNode>
    public var right: Option<AVLNode>

    public init(key: Int64) {
        this.key = key
        this.height = 1
        this.left = Option<AVLNode>.None
        this.right = Option<AVLNode>.None
    }
}

public class AVLTree {
    private var root = Option<AVLNode>.None

    // 获取节点高度
    private func height(node: Option<AVLNode>): Int64 {
        if (node.isNone()) {
            return 0
        } else {
            return node.getOrThrow().height
        }
    }

    // 获取平衡因子
    private func getBalance(node: Option<AVLNode>): Int64 {
        if (node.isNone()) {
            return 0
        } else {
            return height(node.getOrThrow().left) - height(node.getOrThrow().right)
        }
    }

    // 右旋转
    private func rightRotate(y: Option<AVLNode>): AVLNode {
        var x = y.getOrThrow().left
        var T2 = x.getOrThrow().right

        // 执行旋转
        x.getOrThrow().right = y
        y.getOrThrow().left = T2

        // 更新高度
        y.getOrThrow().height = max(height(y.getOrThrow().left), height(y.getOrThrow().right)) + 1
        x.getOrThrow().height = max(height(x.getOrThrow().left), height(x.getOrThrow().right)) + 1

        return x.getOrThrow()
    }

    private func max(a: Int64, b: Int64): Int64 {
        if (a > b) {
            return a
        } else {
            return b
        }
    }

    // 左旋转
    private func leftRotate(x: Option<AVLNode>): AVLNode {
        var y = x.getOrThrow().right
        var T2 = y.getOrThrow().left

        // 执行旋转
        y.getOrThrow().left = x;
        x.getOrThrow().right = T2;

        // 更新高度
        x.getOrThrow().height = max(height(x.getOrThrow().left), height(x.getOrThrow().right)) + 1
        y.getOrThrow().height = max(height(y.getOrThrow().left), height(y.getOrThrow().right)) + 1

        return y.getOrThrow()
    }

    // 插入节点
    public func insert(key: Int64): Unit {
        root = insert(root, key)
    }

    private func insert(node: Option<AVLNode>, key: Int64): AVLNode {
        // 1. 执行标准BST插入
        if (node.isNone()) {
            return AVLNode(key)
        }

        if (key < node.getOrThrow().key) {
            node.getOrThrow().left = insert(node.getOrThrow().left, key)
        } else if (key > node.getOrThrow().key) {
            node.getOrThrow().right = insert(node.getOrThrow().right, key)
        } else {
            return node.getOrThrow() // 不允许重复键
        }

        // 2. 更新节点高度
        node.getOrThrow().height = 1 + max(height(node.getOrThrow().left), height(node.getOrThrow().right))

        // 3. 获取平衡因子
        var balance = getBalance(node)

        // 4. 如果不平衡，有4种情况

        // 左左情况
        if (balance > 1 && key < node.getOrThrow().left.getOrThrow().key) {
            return rightRotate(node.getOrThrow())
        }

        // 右右情况
        if (balance < -1 && key > node.getOrThrow().right.getOrThrow().key) {
            return leftRotate(node.getOrThrow())
        }

        // 左右情况
        if (balance > 1 && key > node.getOrThrow().left.getOrThrow().key) {
            node.getOrThrow().left = leftRotate(node.getOrThrow().left.getOrThrow())
            return rightRotate(node.getOrThrow())
        }

        // 右左情况
        if (balance < -1 && key < node.getOrThrow().right.getOrThrow().key) {
            node.getOrThrow().right = rightRotate(node.getOrThrow().right.getOrThrow())
            return leftRotate(node.getOrThrow())
        }

        return node.getOrThrow()
    }

    // 查找最小值节点
    private func minValueNode(node: Option<AVLNode>): AVLNode {
        var current = node
        while (current.getOrThrow().left.isSome()) {
            current = current.getOrThrow().left
        }
        return current.getOrThrow()
    }

    // 删除节点
    public func delete(key: Int64): Unit {
        root = delete(root, key)
    }

    private func delete(r: Option<AVLNode>, key: Int64): Option<AVLNode> {
        var root = r
        // 1. 执行标准BST删除
        if (root.isNone()) {
            return root
        }

        if (key < root.getOrThrow().key) {
            root.getOrThrow().left = delete(root.getOrThrow().left, key)
        } else if (key > root.getOrThrow().key) {
            root.getOrThrow().right = delete(root.getOrThrow().right, key)
        } else {
            // 节点有一个子节点或没有子节点
            if (root.getOrThrow().left.isNone() || root.getOrThrow().right.isNone()) {
                var temp = Option<AVLNode>.None
                
                // 无子节点情况
                if (temp.isNone()) {
                    temp = root
                    root = Option<AVLNode>.None
                } else {
                    // 有一个子节点情况
                    root = temp // 复制子节点内容
                }
            } else {
                // 节点有两个子节点，获取中序后继节点（右子树的最小值）
                var temp = minValueNode(root.getOrThrow().right)

                // 复制中序后继节点的数据
                root.getOrThrow().key = temp.key

                // 删除中序后继节点
                root.getOrThrow().right = delete(root.getOrThrow().right, temp.key)
            }
        }

        // 如果树只有一个节点，直接返回
        if (root.isNone()) {
            return Option<AVLNode>.None
        }

        // 2. 更新节点高度
        root.getOrThrow().height = max(height(root.getOrThrow().left), height(root.getOrThrow().right)) + 1

        // 3. 获取平衡因子
        var balance = getBalance(root)

        // 4. 如果不平衡，有4种情况

        // 左左情况
        if (balance > 1 && getBalance(root.getOrThrow().left) >= 0) {
            return rightRotate(root.getOrThrow())
        }

        // 左右情况
        if (balance > 1 && getBalance(root.getOrThrow().left) < 0) {
            root.getOrThrow().left = leftRotate(root.getOrThrow().left)
            return rightRotate(root.getOrThrow())
        }

        // 右右情况
        if (balance < -1 && getBalance(root.getOrThrow().right) <= 0) {
            return leftRotate(root)
        }

        // 右左情况
        if (balance < -1 && getBalance(root.getOrThrow().right) > 0) {
            root.getOrThrow().right = rightRotate(root.getOrThrow().right)
            return leftRotate(root);
        }

        return root;
    }

    // 中序遍历
    public func inOrder(): Unit {
        inOrder(root)
    }

    private func inOrder(node: Option<AVLNode>): Unit {
        if (node.isSome()) {
            inOrder(node.getOrThrow().left)
            print("${node.getOrThrow().key} ")
            inOrder(node.getOrThrow().right)
        }
    }

    // 前序遍历
    public func preOrder(): Unit {
        preOrder(root)
    }

    private func preOrder(node: Option<AVLNode>): Unit {
        if (node.isSome()) {
            print("${node.getOrThrow().key} ")
            preOrder(node.getOrThrow().left)
            preOrder(node.getOrThrow().right)
        }
    }
}

测试代码

package Algorithm
import Algorithm.avl.*

main(): Int64 {
    let tree = AVLTree()

    // 测试插入
    tree.insert(10)
    tree.insert(20)
    tree.insert(30)
    tree.insert(40)
    tree.insert(50)
    tree.insert(25)

    println("中序遍历:")
    tree.inOrder() // 输出: 10 20 25 30 40 50

    println("\n前序遍历:")
    tree.preOrder() // 输出: 30 20 10 25 40 50

    // 测试删除
    tree.delete(50)
    println("\n删除50和后的中序遍历:")
    tree.inOrder() // 输出: 10 20 25 30 40 
    
    return 0
}

三、小结

本章为大家详细的介绍了仓颉数据结构与算法中平衡二叉树的内容，下一章，为大家带来平衡二叉树练习题的内容。最后，创作不易，如果大家觉得我的文章对学习仓颉数据结构与算法有帮助的话，就动动小手，点个免费的赞吧！收到的赞越多，我的创作动力也会越大哦，谢谢大家🌹🌹🌹！！！