Java数据结构与算法(平衡二叉树)

前言

平衡二叉树是为了提高二叉树的查询速度，通过满足特定的条件来保持其平衡性。平衡二叉树具有以下特点：

• 左子树和右子树的高度差不会大于1，这是为了确保树的高度不会过大，从而减少查询时的磁盘I/O开销，提高查询速度。
• 平衡二叉树上的所有结点的平衡因子（左子树深度减去右子树深度的值）只可能是-1、0和1。这表示树处于平衡状态，没有明显的倾斜。
• 当插入或删除一个结点后，如果破坏了树的平衡性，需要进行相应的旋转操作来调整，以恢复平衡。这包括左旋转和右旋转两种操作。

平衡二叉树的实现原理基于二叉排序树，在构建过程中，每当插入一个结点时，都会检查是否因插入而破坏了树的平衡性。如果破坏了，则找出最小不平衡子树，并在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。

通过这样的机制，平衡二叉树能够有效地保持其结构的平衡，从而在插入、删除和查找等操作中保持较高的效率。

实现原理

平衡二叉树实现的概述：

1. 节点结构：定义节点的结构，包括键值、父节点、左右子节点以及树的高度。
2. 插入操作：
   • 插入一个节点时，首先更新该节点的父节点信息和高度信息。
   • 检查树的平衡性是否被破坏，即节点的平衡因子（左右子树高度差）的绝对值是否大于1。
   • 如果平衡被破坏，找到最小不平衡子树，并进行旋转操作，以恢复树的平衡。
3. 删除操作：
   • 删除一个节点时，首先更新该节点的父节点信息和高度信息。
   • 检查树的平衡性是否被破坏，即节点的平衡因子（左右子树高度）的绝对值是否大于1。
   • 如果平衡被破坏，找到最小不平衡子树，并进行旋转操作，以恢复树的平衡。
4. 查找操作：在树中进行查找操作，利用二叉搜索树的特性进行快速查找。

具体代码实现

class AVLTreeNode {
    int key;
    int height;
    AVLTreeNode left;
    AVLTreeNode right;
 
    AVLTreeNode(int key) {
        this.key = key;
        this.height = 0;
        this.left = this.right = null;
    }
}
 
public class AVLTree {
 
    private AVLTreeNode root;
 
    public AVLTree() {
        root = null;
    }
 
    // 获取以节点为根的树的高度
    private int height(AVLTreeNode node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }
 
    // 更新节点的高度
    private void updateHeight(AVLTreeNode node) {
        node.height = Math.max(height(node.left), height(node.right)) + 1;
    }
 
    // 左旋
    private AVLTreeNode rotateLeft(AVLTreeNode node) {
        AVLTreeNode rightNode = node.right;
        node.right = rightNode.left;
        rightNode.left = node;
        updateHeight(node);
        updateHeight(rightNode);
        return rightNode;
    }
 
    // 右旋
    private AVLTreeNode rotateRight(AVLTreeNode node) {
        AVLTreeNode leftNode = node.left;
        node.left = leftNode.right;
        leftNode.right = node;
        updateHeight(node);
        updateHeight(leftNode);
        return leftNode;
    }
 
    // 左右旋（先左后右）
    private AVLTreeNode rotateLR(AVLTreeNode node) {
        node.left = rotateLeft(node.left);
        return rotateRight(node);
    }
 
    // 右左旋（先右后左）
    private AVLTreeNode rotateRL(AVLTreeNode node) {
        node.right = rotateRight(node.right);
        return rotateLeft(node);
    }
 
    // 插入节点
    public void insert(int key) {
        root = insert(root, key);
    }
 
    // 递归插入并平衡
    private AVLTreeNode insert(AVLTreeNode node, int key) {
        if (node == null) {
            return new AVLTreeNode(key);
        }
 
        if (key < node.key) {
            node.left = insert(node.left, key);
            if (height(node.left) - height(node.right) == 2) {
                if (key < node.left.key) {
                    node = rotateRight(node);
                } else {
                    node = rotateLR(node);
                }
            }
        } else if (key > node.key) {
            node.right = insert(node.right, key);
            if (height(node.right) - height(node.left) == 2) {
                if (key > node.right.key) {
                    node = rotateLeft(node);
                } else {
                    node = rotateRL(node);
                }
            }
        }
 
        updateHeight(node);
        return node;
    }
}

QA:待定