侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

数据结构--平衡二叉树(AVL、红黑树Java实现)

林贤钦
2020-06-26 / 1 评论 / 9 点赞 / 1,481 阅读 / 13,894 字
温馨提示:
本文最后更新于 2021-07-01,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

平衡二叉树

基本介绍

  • 平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树,是一种特殊的二叉排序树, 可以保证查询效率较高。

  • 具有以下特点:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

    本文内容AVL树和红黑树

为什么需要平衡二叉树

因为在某种极端的情况下,二叉树可能变成了链表,比如依次插入 2 1 3 4 5 6 7,如图

这种形态的树,虽然也符合二叉搜索树的特征,但是查找的性能几乎变成了线性查找的性能了,显然不是我们想要的,所以平衡二叉树就诞生了,平衡二叉树能保证左右的高度差。下面就讲平衡二叉树如何通过左旋右旋自旋来保证平衡。

1、AVL树

AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis,他们在1962年的论文《An algorithm for the organization of information》中发表了它。

1.1、特点

  • 本身首先是一棵二叉搜索树。

  • 带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。

也就是说,AVL树,本质上是带了平衡功能的二叉查找树(二叉排序树,二叉搜索树)。

1.2、AVL树的左旋、右旋、自旋

左旋过程

为了能展示左旋,对上面的例子稍微改成{2,1,4,3,5,6,7} ,来看avl树是如何完成左旋保持平衡

  • 步骤一:新建一个结点,令新结点的值=当前结点(根结点)的值

  • 步骤二:新结点的左子结点指向令当前结点(根结点)的左子结点

  • 步骤三:新结点的右子结点指向当前节点(根结点)的右子结点的的左子结点

  • 步骤四:将当前结点(根结点)的值等于当前结点的右子结点的值

  • 步骤五:将当前结点(根结点)的左子结点指向新创建的结点

  • 步骤六:将当前结点(根结点)的右子结点指向当前结点的右子结点的右子结点

    图上的当前结点指的是要左旋的树,不一定是整棵树的根结点,也可能是某个子树的根结点

右旋过程

右旋和左旋的道理一样,只是左右互转,还是以{1,2,3,4,5,6,7}为例子,当然,为了显示更好的展示右旋,插入的顺序为{6,4,7,2,5,3,1}

  • 步骤一:新建一个结点,令新结点的值=当前结点(根结点)的值

  • 步骤二:新结点的右子结点指向令当前结点(根结点)的右子结点

  • 步骤三:新结点的左子结点指向当前节点(根结点)的左子结点的的右子结点

  • 步骤四:将当前结点(根结点)的值等于当前结点的左子结点的值

  • 步骤五:将当前结点(根结点)的右子结点指向新创建的结点

  • 步骤六:将当前结点(根结点)的左子结点指向当前结点的左子结点的左子结点

自旋过程

假如依次插入的数据为{6,3,7,2,4,5,1},左旋和右旋还能满足条件吗?

可以看到,右旋之后,还是无法满足条件,此时变成了右子树高度-左子树高度>1,显然不是我们想要的结果

所以在右旋的时候判断,如果当前结点的左子树的右子树高度>当前结点的左子树的左子树高度(也就是图中以3为根结点,判断右子树是否比左子树高)

这种情况就应当是左子树左旋,然后整个树右旋

上面以根部右旋,左子树左旋的例子,还有另外一种情况,整个树左旋,右子树右旋,这里就不写出来了,画图挺费时间的,举三返一就行了。

1.3、代码实现

AVL树其他代码与搜索二叉树没什么区别,本质上就是一颗特殊的搜索二叉树,所以,左旋右旋只需要在结点的添加结点这个方法的末尾上添加就行,

代码如下

1、首先先提供返回根结点的左子树高度,右子树高度,和自身结点的高度

class Node{
    int value;
    Node left;
    Node right;
    public Node(int value){
        this.value=value;
    }
    //返回该结点为根结点的左子树高度
    public int leftHeight(){
        if (left==null){
            return 0;
        }
        return left.height();
    }
    //返回该结点为根结点的右子树高度
    public int rightHeight(){
        if (right==null){
            return 0;
        }
        return right.height();
    }
    //返回该节点为根结点的树的高度
    public int height(){
        return Math.max(left == null ? 0:left.height(),right == null ? 0 : right.height())+1;
	} 
}    

2、左旋方法

//左旋方法
public void leftRotate(){
    //1.创建新的结点,将当前根结点的值赋予新节点
    Node newNode = new Node(this.value);
    //2.新结点newNode的左结点指向当前结点的左结点
    newNode.left=this.left;
    //3.新结点newNode的右结点,指向当前结点this的右节点的左结点
    newNode.right=this.right.left;
    //4.将当前结点的右节点的值赋予当前结点的值value
    this.value=this.right.value;
    //5.当前结点的左子树指向新结点
    this.left=newNode;
    //6.当前结点的右子树指向当前结点的右子树的右子树
    this.right=this.right.right;
}

3、右旋方法

//右旋方法
public  void rightRotate(){
    Node newNode = new Node(this.value);
    newNode.right=this.right;
    newNode.left=this.left.right;
    this.right=newNode;
    this.value=this.left.value;
    this.left=this.left.left;
}

4、添加结点的时候判断是否需要左旋,右旋以及自旋

//添加结点的方法
//递归的形式添加结点,注意需要满足二叉排序树的要求
public void add(Node node){
    if (node==null){
        return;
    }
    //判断传入的结点的值,和当前子树的根结点的值的关系
    if (node.value<this.value){
        //如果当前结点的左子结点为null
        if (this.left==null){
            this.left =node;
        }else {
            //否则就递归向左子树添加
            this.left.add(node);
        }
    }else {
        if (this.right==null) {
            this.right =node;
        }else {
            this.right.add(node);
        }
    }
    //添加完结点后,右子树高度-左子树高度>1,左旋转
    if (rightHeight() -leftHeight()>1){
        if (right!=null&&right.leftHeight()>right.rightHeight()){
            //先对右子树惊醒左旋转
            right.rightHeight();
        }
        //左旋转
        leftRotate();
    }
    if (leftHeight()-rightHeight()>1){
        if (left!=null&&left.rightHeight()>left.leftHeight()){
            left.leftRotate();
        }
        rightRotate();
    }
}

2、红黑树

2.1、定义

  • 红黑树是一种特定类型的二叉树,它是在计算机科学中用来组织数据比如数字的块的一种结构。若一棵二叉查找树是红黑树,则它的任一子树必为红黑树.
  • 红黑树是一种平衡二叉查找树的变体,它的左右子树高差有可能大于 1,所以红黑树不是严格意义上的平衡二叉树(AVL),但 对之进行平衡的代价较低, 其平均统计性能要强于 AVL 。
  • 由于每一颗红黑树都是一颗二叉排序树,因此,在对红黑树进行查找时,可以采用运用于普通二叉排序树上的查找算法,在查找过程中不需要颜色信息。

2.2、性质

红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

【1】性质1. 节点是红色或黑色。

【2】性质2. 根节点是黑色。

【3】性质3. 每个叶节点是黑色的。

【4】性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

【5】性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点,俗称黑高。

从五大性质可推出:

  • 新加入到红黑树的节点一定为红色节点
  • 如果一个节点存在黑子节点,那么该节点肯定右两个子节点

无论是变色还是左旋右旋,都是为了保证满足上面五个性质

2.3、左旋过程

以某个结点作为支点(旋转结点),其右子结点变为旋转结点的父结点,右子结点的左子结点变为旋转结点的右子结点,左子结点保持不变。

说明:这个是例子,球的上面的线代表父结点,左右线代表左右结点,虚线代表左旋过程,粉球代表旋转前子树的根结点,黄球代表旋转后的根结点,白球代表根结点的父结点(可能为null)

  • 步骤一:将当前节点的右子节点的左子节点赋值 给了当前的右子节点,并且更新当前节点的右子节点的左子节点的父节点为 当前节点

    图中2的右节点变成了3,3的父节点变成了2

  • 步骤二:将当前节点的父节点(不为空时)指向当前节点的右子节点,更新当前节点的右子节点的父节点为当前节点的父节点

    图中2的父节点的子节点指向了4,4的父节点指向了2的父节点

  • 步骤三:将当前节点的右子节点的左子节点指向当前节点,更新结点当前节点的父节点为当前节点的右子节点

  • 图中4的左子节点指向了2,2的父节点指向了4

2.4、右旋过程

以某个结点作为支点(旋转结点),其左子结点变为旋转结点的父结点,左子结点的右子结点变为旋转结点的左子结点,右子结点保持不变

  • 步骤一:将当前节点的右子节点的左子节点 赋值 给了 当前节点的右子节点,并且更新原当前节点的左节点的右子节点的父节点为 当前节点

  • 图中5的父节点变成了6,6的左子节点变成了5

  • 步骤二:将当前节点的父节点(不为空时)指向原当前节点的左节点,更新原当前节点的左节点的父节点为当前节点的父节点

  • 图中4的父节点变成了6的父节点,6的父节点的孩子节点从6变成了4

  • 步骤三:将原当前节点的左子节点的右子节点指向当前节点,更新当前节点的父节点为原当前节点的左子节点

  • 图中4的右子节点指向了6,6的父节点指向了4

2.5、红黑树插入节点情景分析

情景1:红黑树为空树

最简单的一种情景,直接把插入结点作为根结点就行

注意:根据红黑树性质2:根节点是黑色。还需要把插入结点设为黑色。

情景2:插入结点的Key已存在

处理:更新当前节点的值,为插入节点的值

情景3:插入结点的父结点为黑结点

由于插入的结点是红色的,当插入结点的黑色时,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。

情景4:插入节点的父节点为红色

再次回想下红黑树的性质2:根结点是黑色。如果插入节点的父结点为红结点,那么该父结点不可能为根结点,所以插入结点总是存在祖父结点。

这一点很关键,因为后续的旋转操作肯定需要祖父结点的参与。

  • 4.1:叔叔结点存在并且为红结点

    处理:将父节点和叔叔节点变成黑色,爷爷变成红色,再以爷爷节点为当前节点进行操作

  • 4.2:叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点

    • 4.2.1:新插入节点,为其父节点的左子节点(LL红色情况)

      处理:将父节点改成黑色,爷爷节点改成红色,然后对爷爷节点进行右旋操作

    • 4.2.2:新插入节点,为其父节点的右子节点(LR红色情况)

      处理: 对父节点进行左旋,然后父节点为当前节点处理LL红色情况

  • 4.3:叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的右子结点

    • 4.3.1:新插入节点,为其父节点的右子节点(RR红色情况)

      处理:将父节点变成黑色,爷爷节点变成红色,然后对爷爷节点进行左旋操作

    • 4.3.2:新插入节点,为其父节点的左子节点(RL红色情况)

      处理:对父节点进行右旋操作,然后父节点也当前节点处理RR红色情况

2.6、红黑树插入节点图文过程

依次插入数据{50,25,75,15,30,28,27,26,,100,125,40,35},可展示除重复节点外的所有情况,详情在下文

插入数据{50,25,75}

情景1:红黑树为空树

最简单的一种情景,直接把插入结点作为根结点就行

注意:根据红黑树性质2:根节点是黑色。还需要把插入结点设为黑色。

情景3:插入结点的父结点为黑结点

由于插入的结点是红色的,当插入结点的黑色时,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。

继续插入数据{15}

4.1:父节点为红色且叔叔结点存在并且为红结点

处理:将父节点和叔叔结点变成黑色,将爷爷节点变成红色,再以爷爷节点为当前节点进行下轮操作

继续插入数据{30,28,27}

插入情景4.2:父节点为红色且叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点

4.2.1:新插入节点,为其父节点的左子节点(LL红色情况)

处理:将父节点改成黑色,爷爷节点改成红色,然后对爷爷节点进行右旋操作

继续插入数据{26}

插入情景4.2:父节点为红色且叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点

4.2.2:新插入节点,为其父节点的右子节点(LR红色情况)

对父节点进行左旋操作,将父节点设置为当前节点,然后按照LL红色情况处理

插入情景4.2:父节点为红色且叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点

4.2.1:新插入节点,为其父节点的左子节点(LL红色情况)

处理:将父节点改成黑色,爷爷节点改成红色,然后对爷爷节点进行右旋操作

继续插入数据{100,125}

插入情景4.2:父节点为红色且叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点

4.3.1:新插入节点,为其父节点的右子节点(RR红色情况)

处理:将父节点改成黑色,爷爷节点改成红色,然后以爷爷节点进行左旋操作

继续插入数据{40,35}

插入情景4.2:父节点为红色且叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点

4.3.2:新插入节点,为其父节点的右子节点(RL红色情况)

处理:对父节点进行右旋操作,然后将父节点设置为当前节点,得到RR红色情况,在根据RR情况进行操作

2.7、红黑树添加节点代码详情

自己改的简单版红黑树,仅供参考~

红黑树的基本信息(简单版)

public class RBTree<K extends Comparable<K>,V>{
    //定义颜色常量
    private static final boolean RED = true;
    private static final boolean BLACK =  false;
    //红黑树树根
    private RBNode root;

    public RBNode getRoot(){
        return root;
    }
   /**
     * 红黑树
     * @param <K> key
     * @param <V> value
     */
    static class RBNode<K extends Comparable<K>,V>{
        //颜色
        private boolean color;
        //左子节点
        private RBNode left;
        //右子节点
        private RBNode right;
        //父节点
        private RBNode parent;
        //key
        private K key;
        //value
        private V value;  
        public RBNode() {}
    }    
}

左旋过程

private void leftRotate(RBNode node){
    RBNode right = node.right;
    //将当前节点node的右节点right的左节点 与 当前节点挂父子关系,替代node的右节点
    node.right=right.left;
    if (right!=null){
        right.left.parent=node;
    }
    //将node的父节点与node的右节点挂父子关系
    if (node.parent!=null) {
        if (node == node.parent.left) {
            node.parent.left = right;
        } else {
            node.parent.right = right;
        }
        right.parent=node.parent;
    }
    //将node和right互换身份
    node.parent=right;
    right.left=node;
}

右旋过程

private void rightRotate(RBNode node){
    RBNode left = node.left;
    //将left的右子树和node挂父子关系,代替node和left的位置
    node.left=left.right;
    if (left.right!=null){
        left.right.parent=node;
    }
    //将node的父节点挂到left上面
    left.parent=node.parent;
    if (node.parent!=null){
        if (node==node.parent.left){
            node.parent.left=left;
        }else {
            node.parent.right=left;
        }
    }
    //更新node和left的关系
    node.parent=left;
    left.right=node;
}

插入后修复红黑树平衡的方法

  • |---情景1:红黑树为空树
  • |---情景2:插入节点的key已经存在
  • |---情景3:插入节点的父节点为黑色
  • 情景4 需要咱们去处理
  • |---情景4:插入节点的父节点为红色
  • |---情景4.1:叔叔节点存在,并且为红色(父-叔 双红)
  • |---情景4.2:叔叔节点不存在,或者为黑色,父节点为爷爷节点的左子树
  • |---情景4.2.1:插入节点为其父节点的左子节点(LL情况)
  • |---情景4.2.2:插入节点为其父节点的右子节点(LR情况)
  • |---情景4.3:叔叔节点不存在,或者为黑色,父节点为爷爷节点的右子树
  • |---情景4.3.1:插入节点为其父节点的右子节点(RR情况)
  • |---情景4.3.2:插入节点为其父节点的左子节点(RL情况)

情景1 ,2 在添加节点过程都已经处理,而情景3是不需要处理的,

所以,这个方法是处理情景4的六种情况,有个必要条件就是父节点不为空,且父节点为红色,而父节点为红色,那必定有爷爷节点

private void insertFitUp(RBNode node) {
    //获取当前节点的父节点,前面判空,这里不用判空
    RBNode parent = node.parent;
    //必要条件,父节点不为空,且父节点为红色
    if (parent!=null&&parent.color==RED){
        //获取爷爷节点
        RBNode gParent= parent.parent;
        //分两种情况,父亲节点是爷爷节点的左节点还是右节点
        if (parent==gParent.left){//父亲节点是爷爷节点的左节点
            RBNode uncle = parent.right;
            //第一种情况,叔叔节点不为空,且叔叔节点为红色
            if (uncle!=null&&uncle.color==RED){
                //将父节点,叔叔节点变成黑色,爷爷节点变成红色,然后以爷爷节点为当前节点递归
                uncle.color=BLACK;
                parent.color=BLACK;
                gParent.color=RED;
                insertFitUp(gParent);
                return;
            }else {//叔叔节点为空,或者叔叔节点为黑色
                //这里分两种情况,一是当前节点是父节点的左节点,二是当前节点是父节点的右节点
                if (node==parent.left){//ll情况
                    //将父节点变成黑色,爷爷几点变成红色,然后右旋爷爷节点
                    parent.color=BLACK;
                    gParent.color=RED;
                    //TODO: 右旋
                    rightRotate(gParent);
                }else {//lr情况
                    //左旋父节点
                    leftRotate(parent);
                    //然后以父节点进行递归
                    insertFitUp(parent);
                    return;
                }
            }
        }else {//父亲节点是爷爷节点的右节点
            RBNode uncle = gParent.right;
            if (uncle!=null&&uncle.color==RED){
                parent.color=BLACK;
                uncle.color=BLACK;
                gParent.color=RED;
                insertFitUp(gParent);
            }else {
                if (node==parent.left){
                    //RL情况,右旋父节点
                    rightRotate(parent);
                    insertFitUp(parent);
                    return;
                }else {
                    parent.color=BLACK;
                    gParent.color=RED;
                    leftRotate(gParent);
                }
            }
        }
    }
    this.root.color=BLACK;
}

添加节点的方法

public void insert(K key,V value){
    //创建节点的基本信息
    RBNode node = new RBNode();
    node.key=key;
    node.value=value;
    //新节点一定为红色
    node.color=RED;
    insert(node);
}
private void insert(RBNode node){
    //如果节点为空,直接return
    if (node==null){
        return;
    }
    if (this.root==null){
        //根节点为null,将节点设置为黑色,直接添加在根节点上,然后直接return
        this.root=node;
        this.root.color=BLACK;
        return;
    }
    RBNode parent =null;
    RBNode x = this.root;
    while (x!=null){
        parent=x;
        int cmp = node.key.compareTo(parent.key);
        if (cmp<0){
            //比parent小
            x=x.left;
        }else if (cmp==0){
            //找到key相等,改变值,然后直接return
            x.value=node.value;
            return;
        }else {
            x=x.right;
        }
    }
    //找到了最后结果,x为要插入的点,parent为x的父节点,设置x和parent的关系
    node.parent=parent;
    if (node.key.compareTo(parent.key)<0){
        parent.left=node;
    }else {
        parent.right=node;
    }
    //最后就是维护红黑树。
    insertFitUp(node);
}

9

评论区