红黑树的特性简单记

左手的ㄟ右手 2023-02-13 05:42 58阅读 0赞

## 7.说说红黑树的特性 ##

**红黑树**：属于不严格平衡二叉树，主要解决了平衡二叉树每次插入、删除节点后需要立马操作保证平衡的特性，从而减低了开销。**红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。**  
红黑树主要用红黑两种颜色改变了平衡二叉树左右子树高度差必须小于或等于1的规定，红黑树的特点主要如下：

## **记住：黑根黑叶路同黑，红黑二色红生黑**。 ##

> 1.（二色）节点只有两种颜色，红色和黑色  
> 2.（黑根）根节点只能是黑色  
> 3.（黑叶）每个叶子节点也都是黑色  
> 4.（路同黑）每一个节点到该节点的叶子节点的每条路劲上都包含数量相同的黑色节点。  
> 5.（红生黑）如果一个节点是红色的，那么他的子节点必须是黑色。

红黑树在搜索、查找中因为非平衡的原因会稍逊与平衡二叉树，但是红黑树对插入删除的折中处理大大降低了重复平衡的操作开销，从这一点上来看是值得的。这也就是为什么**STL中的map、set,java中的TreeSet、HashMap**的底层搜索树都是用红黑树的结构来存储数据。

**红黑树什么情况需要变色，什么情况需要旋转？**  
当插入新节点违背了红黑树的定义的时候，尝试把红色节点变为黑色，或者把黑色节点变为红色。  
当着色之后也不能符合红黑树的定，就只能通过左旋转和右旋转来使得新树来符合红黑树的定义了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dKUUpGSg_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dKUUpGSg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200731102338461.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dKUUpGSg==,size_16,color_FFFFFF,t_70