二叉查找树

一棵空树,或者是具有下列性质的二叉树:

  1. 若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  2. 若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  3. 左、右子树也分别为二叉排序树;
  4. 没有键值相等的结点。

左小右大的树

平衡二叉树

  1. 它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1
  2. 它的左子树和右子树都是一颗平衡二叉树。

为了实现平衡二叉树,我们有几种方法

  1. 左旋

    右子变父,左孙变右孙

    大于号变成小于号

  2. 右旋

    左子变父,右孙变左孙

    小于号变成大于号

  3. 先左旋再右旋

  4. 先右旋再左旋


经过旋转的树就能保证平衡因子小于1了

那么旋转的本质是什么呢?

答案就是寻找最低最低失衡节点。

我们拿第一种情况来举例,在这种情况下,第一个最低失衡结点是5号结点(左3右1),为了平衡,我们需要右旋

但是有时单纯的找最低失衡结点有可能会失效,比如第三种情况

在这种情况下,第一个最低失衡结点是5号结点(左3右1),但是我们会发现,在这种情况即使进行右旋也不会平衡(从左三右一变成右三左一),对于这种好像大于号(或者小于号)的情况,如果我们还是单纯的左右旋,是无法平衡的。

因此我们需要进行两步调整,首先,我们要先分析出到底是左孙还是右孙高,比如带三种情况的大于号情况,是右孙高,所以我们要先对左子进行左旋,再对根节点右旋

public class AVLNode {
    //定义结点
    public int data;//保存节点数据
    public int depth;//保存节点深度
    public int balance;//是否平衡
    public AVLNode parent;//指向父节点
    public AVLNode left;//指向左孩子
    public AVLNode right;//指向右孩子

    public AVLNode(int data) {
        this.data = data;
        depth = 1;
        balance = 0;
        left = null;
        right = null;
    }


    //插入数据
    public void insert(AVLNode root, int data) {
        //如果插入的数据小于根节点,插在根节点左侧
        if (data < root.data) {
            //判断根节点的左侧结点是否为空,如果不为空,则递归调用插入
            if (root.left != null) {
                //将根节点的左侧当为新的根节点
                insert(root.left, data);

            } else {
                //如果左侧结点不为空,则新建一个结点赋给左侧
                root.left = new AVLNode(data);
                //让左侧的父母为根节点
                root.left.parent = root;
            }
            //如果插入的数据大于根节点,插在根节点右侧
        } else {
            if (root.right != null) {
                insert(root.right, data);
            } else {
                //如果右侧结点不为空,则新建一个结点赋给右侧
                root.right = new AVLNode(data);
                //让右侧的父母为根节点
                root.right.parent = root;
            }
        }

        //计算root的平衡因子,注意,在上面有递归调用,所以每一个结点的平衡因子都被计算过,每一次递归都会判断是否需要旋转
        root.balance = calcBalance(root);
        //如果左侧高,则进行右旋
        if (root.balance >= 2) {
            //如果右孙高,先左旋
            if (root.left.balance == -1) {
                left_rotate(root);
            }
            right_rotate(root);
        }
        //右侧高,左旋
        if (root.balance <= -2) {
            //左孙高,先右旋
            if (root.right.balance == -1){
                right_rotate(root);
            }
            left_rotate(root);
        }
    }

    //旋转只会改变最低失衡节点的平衡因子
    //右旋
    public void right_rotate(AVLNode p) {
        AVLNode pParent = p.parent;
        AVLNode pLeftSon = p.left;
        AVLNode pRightGrandSon = pLeftSon.right;

        //左子变父
        //小心祖父是空的可能性
        //先让祖父与左子产生联系
        //先让左子的父母节点指向祖父
        pLeftSon.parent = pParent;
        //如果祖父结点不为空,再让祖父的子节点指向左子
        //小心,要判断是左子还是右子
        if (pParent != null) {
            //如果p是祖父的左子
            if (p == pParent.left) {
                pParent.left = pLeftSon;
            } else if (p == pParent.right) {
                pParent.right = pLeftSon;
            }
        }
        //再让p点变为右子(需要双方承认)
        pLeftSon.right = p;
        p.parent = pLeftSon;

        //右孙变左孙
        //注意,左孙可能为空
        p.left = pRightGrandSon;
        if (pRightGrandSon != null) {
            pRightGrandSon.parent = p;
        }

        //注意此处,只有p点和左子的深度有变化,因此只需要改改动这两者的深度和平衡因子
        p.depth = calcDepth(p);
        p.balance = calcBalance(p);
        pLeftSon.depth = calcDepth(pLeftSon);
        pLeftSon.balance = calcBalance(pLeftSon);
    }

    public void left_rotate(AVLNode p) {
        AVLNode pParent = p.parent;
        AVLNode pRightSon = p.right;
        AVLNode pLeftGrandSon = pRightSon.left;

        //右子变父
        pRightSon.parent = pParent;
        //如果祖父结点不为空,再让祖父的子节点指向左子
        //小心,要判断是左子还是右子
        if (pParent != null) {
            //如果p是祖父的左子
            if (p == pParent.left) {
                pParent.left = pRightSon;
            } else if (p == pParent.right) {
                pParent.right = pRightSon;
            }
        }
        //再让p点变为右子(需要双方承认)
        pRightSon.right = p;
        p.parent = pRightSon;

        //左孙变右孙
        p.right = pLeftGrandSon;
        if (pLeftGrandSon != null) {
            pLeftGrandSon.parent = p;
        }

        p.depth = calcDepth(p);
        p.balance = calcBalance(p);
        pRightSon.depth = calcDepth(pRightSon);
        pRightSon.balance = calcBalance(pRightSon);

    }

    //计算平衡因子
    public int calcBalance(AVLNode p) {
        int left_depth;
        int right_depth;
        //左子树深度
        if (p.left != null) {
            left_depth = p.left.depth;
        } else {
            left_depth = 0;
        }
        //右子树深度
        if (p.right != null) {
            right_depth = p.right.depth;
        } else {
            right_depth = 0;
        }
        //返回左子树深度减去右子树深度,就是根节点的平衡因子
        return left_depth - right_depth;
    }

    //计算深度
    public int calcDepth(AVLNode p) {
        int depth = 0;
        if (p.left != null) {
            depth = p.left.depth;
        }
        if (p.right != null && p.right.depth > depth) {
            depth = p.right.depth;
        }
        depth++;
        return depth;
    }

    public static void main(String[] args) {
        AVLNode avlNode = new AVLNode(1);
        avlNode.insert(avlNode, 2);
        avlNode.insert(avlNode, 3);
        avlNode.insert(avlNode, 5);
    }
}

醉后不知天在水,满船清梦压星河