原创

平衡二叉树(AVL树)

定义

平衡二叉树是一种二叉排序树,其中每一个结点的左子树和右子树的高度差至多等于1。

平衡二叉树的前提是一棵二叉排序树,二叉排序树的查找性能受树的形状影响较大,所以需要对二叉排序树进行平衡处理,常见的方法有AVL、红黑树、Treap等。

平衡因子

平衡二叉树上的结点左子树的深度减去右子树的深度的值成为该结点的平衡因子,平衡因子取值只能为0,-1,1。

最小不平衡子树

距离插入结点最近的,且以平衡因子的绝对值大于1的结点为根结点的子树。

平衡二叉树的平衡过程

  • RR型旋转:插入结点在最小不平衡子树的左子树的左子树。
    即当最小不平衡子树根结点的平衡因子大于1时,该子树右旋。
  • LL型旋转:插入结点在最小不平衡子树的右子树的右子树。
    LL型旋转当最小不平衡子树根结点的平衡因子小于1时,该子树左旋。
  • 插入结点后,最小不平衡子树的平衡因子与它的子树的平衡因子符号相反时,需要对它的子树先进行一次旋转,再对它本身反向旋转一次才能完成平衡操作。
    • LR型旋转:插入结点在最小不平衡子树的左子树的右子树。
    • RL型旋转:插入结点在最小不平衡子树的右子树的左子树。

右旋(RR)步骤:

右旋
p为最小不平衡树结点

  • 1 l存储p的左子节点
  • 2 将p左子树(l)的右子节点作为p的左子节点
  • 3 将p设置为p的左子树(l)的右子节点(注意可能为null)的父节点
  • 4 p的父节点作为p的左子树(l)的父节点
    • 如果p的父节点为null,p的左子节点(l)就是root节点
    • 如果p是父节点的左子节点,p的父节点的左子节点替换为l
    • 如果p是父节点的右子节点,p的父节点的右子节点替换为l
  • 5 p为l的右节点
  • 6 l为p的父节点

左旋(LL)步骤:

左旋
p为最小不平衡树结点

  • 1 r存储p的左子节点
  • 2 将p右子树(r)的左子节点作为p的左子节点
  • 3 将p设置为p的右子树(r)的左子节点(注意可能为null)的父节点
  • 4 p的父节点作为p的右子树(r)的父节点
    • 如果p的父节点为null,p的右子节点(r)就是root节点
    • 如果p是父节点的左子节点,p的父节点的左子节点替换为r
    • 如果p是父节点的右子节点,p的父节点的右子节点替换为r
  • 5 p为r的左节点
  • 6 r为p的父节点

左旋(LR)步骤:

p为最小不平衡树结点,l为p的左子结点

  • l节点左旋
  • p节点右旋

左旋(RL)步骤:

p为最小不平衡树结点,r为p的右子结点

  • r节点右旋
  • p节点左旋

示意图:
依次插入3,2,1,4,5,6,7,10,9,8,结点上方数字代表平衡因子。虚线框代表最小不平衡子树。

步骤:

  1. 插入3结点、2结点。
  2. 插入1时,最小不平衡树3结点的平衡因子为2,需要右旋(大于1)。
    file
  3. 插入4结点。
  4. 插入5结点时,最小不平衡树3结点的平衡因子为-2,需要左旋(小于-1)。
    file
    左旋处理:
    file
  5. 插入6结点时,2结点的平衡因子为-2,需要左旋
    file
    左旋处理:
    file
  6. 插入7结点时,5结点的平衡因子为-2,需要左旋。
    file
    左旋处理:
    file
  7. 插入10结点
  8. 插入9结点,最小不平衡树7结点的平衡因子为-2,其子结点10的平衡因子为1且符号不同,所以10为根结点的子树进行右旋,再对最小不平衡子树进行左旋处理。
    file
    最小不平衡树进行右旋、左旋处理:
    file
  9. 插入结点8时,最小不平衡树6结点的平衡因子为-2,其子节点9的平衡因子为1且符号不通,所以对9结点进行右旋,在进行左旋处理。
    file
    最小不平衡树进行右旋、左旋处理:
    file

示例代码:

/**
 * @author weilai
 * @email 352342845@qq.com
 * @date 2020/2/23 8:17 下午
 */
public class BalanceBinaryTree {

    private static class Node {
        // 数据
        public int data;

        // 平衡因子
        public int balance = 0;

        // 左右孩子结点
        public Node lchild, rchild;

        // 父母结点
        public Node parent;

        public Node() {
        }

        public Node(int data, Node parent) {
            this.data = data;
            this.parent = parent;
        }

    }

    //根结点
    public Node root;

    //树大小
    private int size = 0;

    public BalanceBinaryTree() {
        root = null;
    }

    //二叉平衡树插入结点
    public boolean add(int value) {
        Node current = root;
        // 空树情况
        if (current == null) {
            root = new Node(value, null);
            size = 1;
            return true;
        }
        //插入的结点已存在时直接返回
        if (search(value)) {
            return false;
        }
        Node parent = null;
        // while循环找到待插入结点的父结点
        while (current != null) {
            parent = current;
            if (value < current.data) {
                current = current.lchild;
            } else if (value > current.data) {
                current = current.rchild;
            } else {
                break;
            }
        }

        // 每插入一个结点,都需要调整该结点的父结点以及父结点的父结点的平衡因子,直到根结点为止
        Node child = new Node(value, parent);
        if (value < parent.data) {
            parent.lchild = child;
        } else {
            parent.rchild = child;
        }

        // 修改各个父结点的平衡因子
        while (parent != null) {
            int cmp = parent.data - value;
            if (cmp > 0) {
                // 插入左结点则平衡因子+1
                parent.balance++;
            } else {
                // 插入的是右结点,平衡因子-1
                parent.balance--;
            }

            // 结点的平衡因子0时,该结点及其父结点都不需要做修改
            if (parent.balance == 0) {
                break;
            }
            // 结点的平衡因子为2或-2时二叉排序树不平衡,需要旋转调整
            if (Math.abs(parent.balance) == 2) {
                fixAfterInsert(parent);
                break;
            }
            parent = parent.parent;
        }
        size++;
        return true;
    }

    public void fixAfterInsert(Node p) {
        // 左子树深度较大导致的不平衡,左平衡算法右旋
        if (p.balance == 2) {
            // 平衡因子为2时说明左子树导致不平衡,进行左平衡
            leftBalance(p);
        }
        if (p.balance == -2) {
            // 平衡因子为-2说明右子树导致不平衡,进行右平衡
            rightBalance(p);
        }
    }

    // 左平衡,p为最小不平衡子树的根结点
    public void leftBalance(Node p) {
        //最小不平衡子树根结点的左孩子
        Node lc = p.lchild;
        switch (lc.balance) {
            //插入的结点在p的左孩子的左子树上,需要右单旋处理
            case 1:
                lc.balance = 0;
                p.balance = 0;
                //右单旋
                rightRotate(p);
                break;
            //插入的结点在p的左孩子的右子树上,需要双旋(先左旋再右旋)处理
            case -1:
                //rd指向p的左孩子的右子树树根
                Node rd = lc.rchild;
                //修改最小不平衡二叉树根结点p以及p的左孩子lc的平衡因子
                switch (rd.balance) {
                    case 1:
                        lc.balance = 0;
                        p.balance = -1;
                        break;
                    case -1:
                        lc.balance = 1;
                        p.balance = 0;
                        break;
                    case 0:
                        lc.balance = 0;
                        p.balance = 0;
                        break;
                    default:
                        throw new IllegalStateException("Unexpected value: " + rd.balance);
                }
                rd.balance = 0;
                //双旋
                leftRotate(p.lchild);      //对p的左子树作左旋处理(p的左孩子为空时不操作)
                rightRotate(p);            //对p作右旋处理
                break;
            default:
                throw new IllegalStateException("Unexpected value: " + lc.balance);
        }
    }

    //右平衡,p为最小不平衡子树的根
    public void rightBalance(Node p) {
        //rc指向p的右孩子
        Node rc = p.rchild;
        switch (rc.balance) {
            //插入的结点在p的右孩子的右子树上时,进行左单旋处理
            case -1:
                rc.balance = 0;
                p.balance = 0;
                //左单旋
                leftRotate(p);
                break;
            //插入的结点在p的右孩子的左子树上时,进行双旋处理(先右旋再左旋)
            case 1:
                //ld指向p的右孩子的左子树的树根
                Node ld = rc.lchild;
                switch (ld.balance) {
                    case 1:
                        p.balance = 0;
                        rc.balance = -1;
                        break;
                    case -1:
                        p.balance = 1;
                        rc.balance = 0;
                        break;
                    case 0:
                        p.balance = 0;
                        rc.balance = 0;
                        break;
                    default:
                        throw new IllegalStateException("Unexpected value: " + ld.balance);
                }
                ld.balance = 0;
                //双旋操作
                rightRotate(p.rchild);     //对p的右子树进行右旋处理
                leftRotate(p);                 //对p进行左旋处理
                break;
            default:
                throw new IllegalStateException("Unexpected value: " + rc.balance);
        }
    }

    // 左旋(逆时针旋转)
    // 1。r存储p的左子节点
    // 2。将p右子树(r)的左子节点作为p的左子节点
    // 3。将p设置为p的右子树(r)的左子节点(注意可能为null)的父节点
    // 4。p的父节点作为p的右子树(r)的父节点
    //   - 如果p的父节点为null,p的右子节点(r)就是root节点
    //   - 如果p是父节点的左子节点,p的父节点的左子节点替换为r
    //   - 如果p是父节点的右子节点,p的父节点的右子节点替换为r
    // 5。p为r的左节点
    // 6。r为p的父节点
    public void leftRotate(Node p) {
        if (p != null) {
            Node r = p.rchild;
            //将p的右子树的左孩子作为p的右孩子
            p.rchild = r.lchild;
            //p的右子树的左孩子不为空时,将p作为其父结点
            if (r.lchild != null) {
                r.lchild.parent = p;
            }
            //r结点左旋称为成为根结点(r指向p.parent)
            r.parent = p.parent;
            //p的父结点指向r结点
            if (p.parent == null) {
                root = r;
            } else if (p == p.parent.lchild) {
                p.parent.lchild = r;
            } else if (p == p.parent.rchild) {
                p.parent.rchild = r;
            }
            //p结点左旋成为r的左孩子
            r.lchild = p;
            //p的父结点是r
            p.parent = r;
        }
    }

    // 右旋(顺时针旋转)
    // 1。l存储p的左子节点
    // 2。将p左子树(l)的右子节点作为p的左子节点
    // 3。将p设置为p的左子树(l)的右子节点(注意可能为null)的父节点
    // 4。p的父节点作为p的左子树(l)的父节点
    //   - 如果p的父节点为null,p的左子节点(l)就是root节点
    //   - 如果p是父节点的左子节点,p的父节点的左子节点替换为l
    //   - 如果p是父节点的右子节点,p的父节点的左子节点替换为l
    // 5。p为l的右节点
    // 6。l为p的父节点
    public void rightRotate(Node p) {
        if (p != null) {
            //l为p的左孩子
            Node l = p.lchild;
            //将p的左子树的右孩子作为p的左孩子
            p.lchild = l.rchild;
            //当p的左子树的右孩子不为空时,将p作为它的父结点
            if (l.rchild != null) {
                l.rchild.parent = p;
            }

            // p的父节点作为p的左子树父节点
            l.parent = p.parent;
            // 如果p.parent为null,则p就是根节点
            if (p.parent == null) {
                root = l;
            }
            // 如果p是其父节点的左子节点,则l作为p父亲节点的左子节点
            else if (p == p.parent.lchild) {
                p.parent.lchild = l;
            }
            // 如果p是其父节点的右子节点,则l作为p父亲节点的右子节点
            else if (p == p.parent.rchild) {
                p.parent.rchild = l;
            }
            // p为l的右节点
            l.rchild = p;
            // l为p的父节点
            p.parent = l;
        }
    }

    //二叉平衡树查找
    public boolean search(int value) {
        Node current = root;
        while (current != null) {
            if (value > current.data) {
                current = current.rchild;
            } else if (value < current.data) {
                current = current.lchild;
            } else {
                return true;
            }
        }
        return false;
    }

    //获取树中的结点数
    public int size() {
        return size;
    }

    // 中序遍历
    public void inOrderTraverse() {
        inOrderTraverse(root);
    }

    // 中序遍历
    public void inOrderTraverse(Node node) {
        if (node == null) {
            return;
        }
        inOrderTraverse(node.lchild);
        System.out.print(node.data + " ");
        inOrderTraverse(node.rchild);
    }
}

使用:

public class Test {

    public static void main(String[] args) {
        BalanceBinaryTree tree = new BalanceBinaryTree();
        tree.add(3);
        tree.add(2);
        tree.add(1);
        tree.add(4);
        tree.add(5);
        tree.add(6);
        tree.add(7);
        tree.add(10);
        tree.add(9);
        tree.add(8);
        tree.inOrderTraverse();
        System.out.println(tree.search(12));
    }
}

file

正文到此结束
本文目录