AVL Tree - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

入门链接

五分钟告诉你什么是平衡二叉树 ？什么是二叉排序树？平衡因子的计算等等 平衡二叉排序树|AVL树-从入门到入土 二叉平衡树AVL平衡调整数据结构 平衡二叉树（AVL树） 调整 大一统 极简方法讲解

详解

什么是平衡二叉树（AVL） java数据结构与算法之平衡二叉树(AVL树)的设计与实现 示例代码 图解：什么是AVL树？（删除总结篇） Difference between the time complexity required to build Binary search tree and AVL tree?

平衡操作（分类和旋转）

标准写法

public class AVLNode<T> {

    // 左结点
    public AVLNode<T> left;

    // 右结点
    public AVLNode<T> right;

    // 存储的数据
    public T data;

    // 当前结点的高度
    public int height;

    // 一个没有叶节点的节点
    public AVLNode(T data) {
        this(null, null, data);
    }

    // 一个有叶节点的节点，且当前节点的高度为0
    public AVLNode(AVLNode<T> left, AVLNode<T> right, T data) {
        this(left, right, data, 0);
    }

    // 一个有叶节点的特定高度的节点
    public AVLNode(AVLNode<T> left, AVLNode<T> right, T data, int height) {
        this.left = left;
        this.right = right;
        this.data = data;
        this.height = height;
    }
}

AVL树高度和结点的关系（详见Tutorial 4 Problem 1.b.）

证明：一个有n个结点的AVL树的最高的高度h < 2log(n)