一起学算法（红黑树篇）

深藏阁楼爱情的钟 2023-10-09 23:47 3阅读 0赞

分享一个动画展示的网址：[Red/Black Tree Visualization (lerogo.com)][Red_Black Tree Visualization _lerogo.com]

将红黑树之前，我们先来了解一下什么叫做2-3树！！！

在我们以前学习的过程中（二分搜索树、完全二叉树等）结点都是存放了一个元素，2、3树中结点可以存放一个元素或者两个元素

![cdb6c6ee9b9a43c5a87f99f1f15324a3.png][]

因此每个结点都有2个或者3个孩子，这种的树叫做2-3树

![6bbb7e80a3f149d3b1d5c513fe894b8e.png][]

**重要性质**：

1.2-3树是一棵绝对平衡的树

2.添加操作时永远不会添加到空的位置上去，根结点除外

下面给大家演示2-3树的添加操作过程（以上面的图为例）：

*  添加42

![529744422dda4ba282a21960953d68ff.png][]

*  添加37

![c1725d6a4f8c4cc98e2f9ee7d216b80e.png][]

*  添加12

![08d4e72ba3d54289ae16fbcdf1bd8449.png][]

![7b4e5350f6864a1f938fd252152ce931.png][]

*  添加18

![55ca3dad951b4c1e846e870b215fd0d5.png][]

*  添加6

![98950553619f428093732a4d63bb9454.png][]

*  添加11

![734a31f2f7804ea5b41c4f41fba18ce5.png][]

*  添加5

![c0959057dccf4b3b815d5eda63ddb911.png][]

**红黑树与2-3树的等价性**：

![852293739aad4135a85a057117bf86fd.png][]

我们现在将这个2-3树转换为红黑树，如图所示：

![4558df1683804ec683d7387440c1432c.png][]

从上图中我们可以得到红黑树的以下性质：

1.  内个结点要么是红色、要么是黑色
2.  红黑树的根节点一定是黑色的
3.  每个叶子结点（最后的空节点）是黑色的
4.  红色结点的左右孩子一定为黑色
5.  任意结点到叶子结点中所经历的黑色结点的个数相同

**注意**：

1.严格意义上来讲，红黑树不是平衡二叉树，而是保持“黑平衡”的二叉树

2.时间复杂度为O(logn)

下面附构造红黑树的源代码：

public class RbTree<T extends Comparable<T>> {
        private class Node<T>{
            T val;
            Node left;
            Node right;
            int count;
            //节点的颜色
            boolean isRed;
    
            public Node(T val){
                this.val=val;
                this.left=this.right=null;
                this.isRed=true;//新创建的结点颜色为红色的（有可能是融合结点）
                this.count=1;
            }
        }
        //根节点
        private Node<T> root;
        private int size;
    
        //判断是否为空
        public boolean isEmpty(){
            return this.size==0;
        }
        //获取结点的个数
        public int getSize(){
            return this.size;
        }
    
        //添加元素
        public void add(T val){
            this.root=add(this.root,val);
            //更新根节点颜色
            this.root.isRed=false;
        }
    
       //左旋
        public Node leftRotate(Node node){
            Node x=node.right;
            node.right=x.left;
            x.left=node;
            //旋转结点的颜色等于原结点的颜色
            x.isRed=node.isRed;
            //原结点的颜色设为红色
            node.isRed=true;
            return x;
        }
    
        //右旋
        public Node rightRotate(Node node){
            Node x=node.left;
            node.left=x.right;
            x.right=node;
            x.isRed=node.isRed;
            node.isRed=true;
            return x;
        }
    
        //颜色反转
        public void flipColor(Node node){
            node.left.isRed=node.right.isRed=false;
            node.isRed=true;
        }
    
        //获取结点颜色的方法
        public boolean getColor(Node node){
            if(node==null){
                return false;
            }
            return node.isRed;
        }
    
        private Node add(Node<T> node,T val){
          //递归到底
            if(node==null){
                this.size++;
                return new Node(val);
            }
            Node result=null;
            //如果结点的值大于val,则在该节点的左树上找，返回的根节点直接挂接在该节点的左数上
            if(node.val.compareTo(val)>0){
               node.left= add(node.left,val);
            } else if(node.val.compareTo(val)<0){
                node.right=add(node.right,val);
            }else{
                node.count++;
            }
            result=node;
    
            //对结果进行处理
            //左旋   当根结点右结点为红色，左结点为黑色时，进行左旋
            if(getColor(result.right)&&!getColor(result.left)){
                result=leftRotate(result);
            }
            //右旋  当根结点的左节点为红，左节点的左节点为红时，进行右旋
            if(getColor(result.left)&&getColor(result.left.left)){
                result=rightRotate(result);
            }
            //颜色反转   当根节点的左右子树都为红时，进行颜色反转
            if(getColor(result.left)&&getColor(result.right)){
                flipColor(result);
            }
           return result;
    
        }
        //层序遍历
        public void levelTraversal() {
            if(this.root==null){
                return;
            }
            Queue<Node> queue = new LinkedList<>();
            queue.offer(this.root);
            while (!queue.isEmpty()) {
                Node node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
    
        }

在红黑树时，左旋与右旋操作：

右旋：

![feb441b621944609aadb4214aa18384f.png][]左旋：

![d8333af3afe34a2fae77cca9466caf48.png][]

红黑树中旋转的情况：

![a82486ec48b84f74b40f7b68916ca64f.png][]

左右旋转之后看看是否符合上述的旋转条件，如果符合继续旋转，直到不符合条件为止停止旋转！！！

**红黑树性能总结**：

*  完全随机的数，二分搜索树已经可以满足我们的日常需求
 *  在查询较多的情况下，AVL树性能较高
 *  在添加较多的情况下，红黑树表现出来的性能较高

想要画一棵红黑树，你可以先画与之对应的2-3树，然后再将2-3树转换为红黑树，直接画红黑树对初学者有些困难，但是相比而言，会直接画红黑树的过程会对你对红黑树有着更好的理解！！！

加油吧骚年！！！

[Red_Black Tree Visualization _lerogo.com]: https://algorithm.lerogo.com/RedBlack.html
[cdb6c6ee9b9a43c5a87f99f1f15324a3.png]: https://img-blog.csdnimg.cn/cdb6c6ee9b9a43c5a87f99f1f15324a3.png
[6bbb7e80a3f149d3b1d5c513fe894b8e.png]: https://img-blog.csdnimg.cn/6bbb7e80a3f149d3b1d5c513fe894b8e.png
[529744422dda4ba282a21960953d68ff.png]: https://img-blog.csdnimg.cn/529744422dda4ba282a21960953d68ff.png
[c1725d6a4f8c4cc98e2f9ee7d216b80e.png]: https://img-blog.csdnimg.cn/c1725d6a4f8c4cc98e2f9ee7d216b80e.png
[08d4e72ba3d54289ae16fbcdf1bd8449.png]: https://img-blog.csdnimg.cn/08d4e72ba3d54289ae16fbcdf1bd8449.png
[7b4e5350f6864a1f938fd252152ce931.png]: https://img-blog.csdnimg.cn/7b4e5350f6864a1f938fd252152ce931.png
[55ca3dad951b4c1e846e870b215fd0d5.png]: https://img-blog.csdnimg.cn/55ca3dad951b4c1e846e870b215fd0d5.png
[98950553619f428093732a4d63bb9454.png]: https://img-blog.csdnimg.cn/98950553619f428093732a4d63bb9454.png
[734a31f2f7804ea5b41c4f41fba18ce5.png]: https://img-blog.csdnimg.cn/734a31f2f7804ea5b41c4f41fba18ce5.png
[c0959057dccf4b3b815d5eda63ddb911.png]: https://img-blog.csdnimg.cn/c0959057dccf4b3b815d5eda63ddb911.png
[852293739aad4135a85a057117bf86fd.png]: https://img-blog.csdnimg.cn/852293739aad4135a85a057117bf86fd.png
[4558df1683804ec683d7387440c1432c.png]: https://img-blog.csdnimg.cn/4558df1683804ec683d7387440c1432c.png
[feb441b621944609aadb4214aa18384f.png]: https://img-blog.csdnimg.cn/feb441b621944609aadb4214aa18384f.png
[d8333af3afe34a2fae77cca9466caf48.png]: https://img-blog.csdnimg.cn/d8333af3afe34a2fae77cca9466caf48.png
[a82486ec48b84f74b40f7b68916ca64f.png]: https://img-blog.csdnimg.cn/a82486ec48b84f74b40f7b68916ca64f.png