【五一创作】红黑树数据结构

这篇具有很好参考价值的文章主要介绍了【五一创作】红黑树数据结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

现在JAVASE中HashMap中底层源码是由数组+链表+红黑树进行设计的,然后很多地方也是用到红黑树,这里单独对红黑树数据结构进行简单的介绍。

目录

红黑树概念

红黑树的性质

自平衡规则

代码


 文章来源地址https://www.toymoban.com/news/detail-448961.html

红黑树概念

红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。

二叉查找树,也称有序二叉树(ordered binary tree),或已排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 任意节点的左、右子树也分别为二叉查找树。 没有键值相等的节点(no duplicate nodes)。 因为一棵由n个结点随机构造的二叉查找树的高度为lgn,所以顺理成章,二叉查找树的一般操作的执行时间为O(lgn)。但二叉查找树若退化成了一棵具有n个结点的线性链后,则这些操作最坏情况运行时间为O(n)。红黑树虽然本质上是一棵二叉查找树,但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡,从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

 

红黑树的性质

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的,则它的两个孩子结点是黑色的
  4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点),任何相邻的节点都不能同时为红色,也就是说,红色节点是被黑色节点隔开的。

自平衡规则

【五一创作】红黑树数据结构

 

代码

红黑树插入
插入操作包括两部分工作:一查找插入的位置;二插入后自平衡。查找插入的父结点很简单,跟查找操作区别不大:
从根结点开始查找;
若根结点为空,那么插入结点作为根结点,结束。
若根结点不为空,那么把根结点作为当前结点;
若当前结点为null,返回当前结点的父结点,结束。
若当前结点key等于查找key,那么该key所在结点就是插入结点,更新结点的值,结束。
若当前结点key大于查找key,把当前结点的左子结点设置为当前结点,重复步骤4;
若当前结点key小于查找key,把当前结点的右子结点设置为当前结点,重复步骤4;

【五一创作】红黑树数据结构

 

package com.example.tree;

public class RBTree<K extends Comparable<K>,V> {
    private static final boolean RED=true;
    private static final boolean BLACK=false;

    private RBNode root;


    static class RBNode<K extends Comparable<K>,V>{
        private RBNode parent;
        private RBNode left;
        private RBNode right;
        private boolean color;
        private K key;
        private V value;

        public RBNode getParent() {
            return parent;
        }

        public void setParent(RBNode parent) {
            this.parent = parent;
        }

        public RBNode getLeft() {
            return left;
        }

        public void setLeft(RBNode left) {
            this.left = left;
        }

        public RBNode getRight() {
            return right;
        }

        public void setRight(RBNode right) {
            this.right = right;
        }

        public boolean isColor() {
            return color;
        }

        public void setColor(boolean color) {
            this.color = color;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }

        public RBNode() {
        }

        public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
            this.parent = parent;
            this.left = left;
            this.right = right;
            this.color = color;
            this.key = key;
            this.value = value;
        }
    }
    //获取父节点
    private RBNode parentof(RBNode rbNode){
        return rbNode!=null?rbNode.parent:null;
    }

    //判断是否为红色
    private boolean isRed(RBNode rbNode){
        return rbNode.color==RED?true:false;
    }

    private boolean isBlack(RBNode rbNode){
        return rbNode.color==RED?false:true;
    }

    private void setRed(RBNode rbNode){
        if(rbNode!=null){
            rbNode.color=RED;
        }
    }

    private void setBlack(RBNode rbNode){
        if(rbNode!=null){
            rbNode.color=BLACK;
        }
    }
    public void inOrder(){
        inOrder(this.root);
    }
    //中序打印
    public void inOrder(RBNode rbNode){
        if(rbNode!=null){
            inOrder(rbNode.left);
            System.out.print(rbNode.key+" ");
            inOrder(rbNode.right);
        }
    }

    //左旋
    private void  leftRotate(RBNode rbNode){
        RBNode right = rbNode.right;
        rbNode.right=right.left;
        if(right.left!=null){
            right.left.parent=rbNode;
        }
        if(rbNode.parent!=null){
            right.parent=rbNode.parent;
            if(rbNode.parent.left==rbNode)
                rbNode.parent.left=right;
            if(rbNode.parent.right==rbNode)
                rbNode.parent.right=right;
        }
        else {
            this.root=right;
        }
        rbNode.parent=right;
        right.left=rbNode;
    }

    //右旋
    private void  rightRotate(RBNode rbNode){
        RBNode left = rbNode.left;
        rbNode.left=left.right;
        if(left.right!=null)
            left.right.parent=rbNode;
        if(rbNode.parent!=null){
            left.parent=rbNode.parent;
            if(rbNode.parent.left==rbNode)
                rbNode.parent.left=left;
            if(rbNode.parent.right==rbNode)
                rbNode.parent.right=left;
        }
        else {
            this.root=left;
        }
        rbNode.parent=left;
        left.right=rbNode;
    }

    public void insert(K key,V value){
        RBNode node=new RBNode();
        node.setKey(key);
        node.setValue(key);
        node.setColor(RED);
        insert(node);
    }
    private void insert(RBNode rbNode){
        RBNode parent=null;
        RBNode x=this.root;
        while (x!=null){
            parent=x;
            int i = rbNode.key.compareTo(x.key);
            if(i>0){
                x=x.right;
            }
            else if(i==0){
                x.setValue(rbNode.getValue());
                return;
            }
            else {
                x=x.left;
            }

        }
        rbNode.parent=parent;
        if(parent!=null){
            int i = rbNode.key.compareTo(parent.key);
            if(i>0){
                parent.right=rbNode;
            }
            else {
                parent.left=rbNode;
            }
        }else {
            this.root=rbNode;
        }
        insertFixup(rbNode);
    }

    private void insertFixup(RBNode node){
        this.root.setColor(BLACK);
        RBNode parent = parentof(node);
        RBNode gparent = parentof(parent);
        if(parent!=null&&isRed(parent)){
            RBNode uncle=null;
            if(parent==gparent.left){
                uncle=gparent.right;
                if (uncle != null && isRed(uncle)) {
                        setBlack(parent);
                        setBlack(uncle);
                        setRed(gparent);
                        insertFixup(gparent);
                        return;
                }
                if(uncle==null||isBlack(uncle)){
                    if(node==parent.left){
                        setBlack(parent);
                        setRed(gparent);
                        rightRotate(gparent);
                        return;
                    }
                    if(node==parent.right){
                        leftRotate(parent);
                        insertFixup(parent);
                        return;
                    }
                }
            }
            else {
                uncle=gparent.right;
                if (uncle != null && isRed(uncle)) {
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gparent);
                    insertFixup(gparent);
                    return;
                }
                if(uncle==null||isBlack(uncle)){
                    if(node==parent.right){
                        setBlack(parent);
                        setRed(gparent);
                        rightRotate(gparent);
                        return;
                    }
                    if(node==parent.left){
                        rightRotate(parent);
                        insertFixup(parent);
                        return;
                    }
                }

            }
        }

    }

注:

Key extends Comparable<Key>:这里相当于使用泛型,但是这里的泛型Key有限制,表示必须实现Comparable<Key>这个接口才能当成参数传递;如Java自带的Integer、String都符合这个要求;而且这种写法只能当成类的泛型使用,这里其实是将泛型Key擦除到它的一个边界
而Comparable 本身是一个接口,如果一个类如:class Key implements Comparable<Integer>{} 也是Comparable的子类,即前后可以不一致;而且Comparable本身一般不做泛型使用;另外Comparable可以当成方法的参数使用。

 

到了这里,关于【五一创作】红黑树数据结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——红黑树

    目录 概念 性质 结点的定义  插入 调整 当p是g的左孩子时 当p为g的右孩子时 插入完整代码 红黑树的检测 红黑树完整代码(包括测试数据)   红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是RED或BLACK。 通过对任何一条从根到叶子的路径

    2023年04月09日
    浏览(42)
  • [数据结构]-红黑树

    前言 作者 : 小蜗牛向前冲 名言: 我可以接受失败,但我不能接受放弃   如果觉的博主的文章还不错的话,还请 点赞,收藏,关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录 一、红黑树的基本知识  1、红黑树的概念 2、性质  二、红黑树的模拟实

    2024年02月04日
    浏览(44)
  • 【数据结构】红黑树

    🐱作者:一只大喵咪1201 🐱专栏:《数据结构与算法》 🔥格言: 你只管努力,剩下的交给时间! 在学习AVL树的时候,我们知道,当修改AVL树的结构(插入,删除)时,会通过旋转来保证平衡因子不超过1,所以频繁的修改结构会导致效率低下,今天我们学习的红黑树就完美解

    2023年04月17日
    浏览(46)
  • 数据结构之红黑树

    数据结构可视化演示链接,也就是图片演示的网址 数据结构之AVL Tree 数据结构之B树和B+树 数据结构之Radix和Trie 数据结构之二叉搜索树 红黑树是一种二叉查找树,但在每个结点上增加了一个存储位表示结点的颜色,可以是RED或者BLACK。通过对任何一条从根到叶子的路径上各个

    2024年01月17日
    浏览(42)
  • 手写红黑树【数据结构】

    2024-3-30 10:52:57 昨天晚上B站看到的视频 00:00~01:00 以下内容源自《【数据结构】》 仅供学习交流使用 禁止其他平台发布时删除以下此话 本文首次发布于CSDN平台 作者是CSDN@日星月云 博客主页是https://jsss-1.blog.csdn.net 禁止其他平台发布时删除以上此话 我红黑树那么牛,你们凭什

    2024年04月25日
    浏览(33)
  • 【数据结构】红黑树详解

    目录 前言: 红黑树的概念: 红黑树的性质: 红黑树节点的定义: 红黑树的插入: 情况1:cur为红,p为红,g为黑,u存在且为红  情况2:cur为红,p为红,g为黑,u不存在或者u为黑(p和cur都在其父亲节点同一侧) 情况3:cur为红,p为红,g为黑,u不存在或者u为黑(p和cur在其父

    2024年04月14日
    浏览(52)
  • 数据结构--红黑树详解

    红黑树(Red Black Tree)是一种自平衡二叉查找树。它是在 1972 年由 Rudolf Bayer 发明的,当时被称为平衡二叉 B 树(symmetric binary B-trees)。后来,在 1978 年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。 由于其自平衡的特性,保证了最坏情形下在 O(logn) 时间复杂度内完

    2024年02月22日
    浏览(44)
  • 数据结构入门-11-红黑树

    史上最负盛名的平衡二叉树–红黑树,但其实就是2-3树的一种实现 也是BST,每一个节点都有颜色 性质 看 后面推导出来的结论 2-3树 :和红黑树是等价的 满足BST的基本性质,但不是一种二叉树 有两种节点: 2-3 绝对平衡:根节点到叶子节点 一定相同 2.3.1 如何维护绝对平衡

    2023年04月17日
    浏览(39)
  • 数据结构——红黑树详解

    红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树 确保没有一条路径会比其他路径长出两倍 ,因而是接近平衡的。(说它是接近平衡因为它并没有像AVL树的

    2024年04月13日
    浏览(38)
  • C++数据结构--红黑树

    红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路 径会比其他路径长出俩倍,因而是接近平衡的。如图所示: 每个结点不是红色就是黑色。

    2024年02月09日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包