数据结构：什么是红黑树？为什么要用红黑树？ 本篇主要谈谈对红黑树的理解，大家都晓得JDK8中的hashmap底层是数组+链表+红黑树实现的，当面试官问你：为啥要加上红黑树实现呢？？ 那我们首先从概念来了解一下： 一、什么是红黑树？ 红黑树是一个接近平衡的二叉查找树，也就是说二叉查找树的特性红黑树应该都具备，那么具备哪些特性呢？ 左子树小于根节点右子树大于根节点左右子树也分别为二叉查找树 换句话就是有序的。那么有什么优点呢？ 
比如我要插入2，该怎么插入呢？ 和5比较，<5，到左侧；和3比较，<3到左侧；和1比较，>1，到1的右侧； 比如查询1呢？该如何查询？其实一思考，查询的过程和插入的过程是一样的，其实也就是二分查找的思想。所查询的次数也就是树的高度。其时间复杂度为logn. 那问题来了，什么是红黑树呢？我们如上举例是一个平衡的二叉树，因为根节点是5。但是当有一个诸如这样的序列：1，4，5，7，8，9那么这个二叉树会变成什么样？ 
那么时间复杂度就变成了O(N),当数据量足够大的情况下,那速度就可想而知。 所以我们便衍生出了红黑树，一个自平衡的二叉树，除了具备二叉树的特性，还具备以下特性： 每个结点不是红色就是黑色不可能有两个红色结点相连，每个叶子都是空的黑结点（null），不存储数据根节点都是黑色root每个结点，从该结点到其可达叶子结点的所有路径，都包含相同数目的黑色结点 
当插入或者删除的时候，红黑树的规则可能就会被打破，那么就得做出一些调整，去维持这些规则。 二、基本操作 1、变色（黑变红，红变黑） 要求： 父节点是红色；叔父节点也是红色； 变更： 将父节点和叔父节点变为黑色；爷爷节点变为红色；把指针指向爷爷节点，变为下一步要操作的结点； 
6是想要插入的数值，发现父和叔节点都是红色，则采用变色处理： 
2、左旋 要求： 当前父节点是红色；叔父节点是黑色；当前的结点是右子树；指针变化到父节点（未旋转之前的父节点） 
上一步已经把指针指向了爷爷节点，我们发现12这个爷爷节点符合左旋的规则，所以进行左旋。 12的父结点变为自己的左结点，自己的左结点给了父节点作为他的右结点。如下图： 
3、右旋 要求 当前父节点是红色；叔父节点是黑色；当前的结点是左子树；以爷爷节点右旋； 变更 父节点变为黑色；爷爷变为红色； 如上例子还未到平衡二叉树，左旋完成之后，将结点指向了操作结点5。5的父节点是红色，叔父节点是黑色，且5是左子树，满足右旋，将爷爷节点变为红色，父节点变为红色，移动位置，如下图： 
如上则完成了红黑树的要求。整个变更流程如下图， 
分析下来，通过插入一个节点对于红黑树的基本操作有了一个基本的了解。所以其时间复杂度都是接近于logn。 三、为何要用红黑树？ 最熟悉的用红黑树的地方就是jdk8对应的hashmap,红黑树其实也是采用的二分法，相比于二叉查找树，可以避免单一链表，腿脚部分的特殊情况的出现。最坏的情况，时间复杂度也就是接近logn。同样的道理，这也是为何不用数组+链表，而又加入了红黑树的原因，也是为了避免链表过长，降低了效率。那为何不直接用红黑树呢？还得加上链表？因为红黑树需要进行左旋，右旋操作， 而单链表不需要。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/59214.html
