红黑树的简单介绍_口语化介绍一下红黑树

简单介绍

红黑树是一种自平衡的二叉查找树，是一种高效的查找树

可以在o(logN)时间内完成查找，增加，删除等操作。比如C++ STL中的map是基于红黑树结构实现的。

性质

普通的二叉查找树在极端情况下可退化为链表，所以此时增删改查效率都比较地下。所以出现了一些自平衡的查找树，比如AVL，红黑树等。这些自平衡的查找树通过定义一些性质，将任意节点的左右子树高度差控制在规定范围内，以达到平衡状态。

红黑树通过如下的性质定义实现自平衡

1.节点是红色或黑色的，根为黑色，所有叶子为黑色（叶子是NULL）

2.每个红色节点必须有两个黑色的子节点（从每个叶子到根的所有路径上不能有两个连续的红色节点）

3.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（简称黑高）？？?

上面几个性质的限制，可以避免二叉查找树退化成单链表的情况。but还需要考虑一些其他问题。如：某个节点到其每个叶子节点路径长度的问题。如果某些路径长度过长，那么在对这些路径上节点进行增删改查操作时，效率也会大大降低（说法不精确）

在红黑树简介一节中说到红黑树被发明出来的时候并不叫红黑树，而是叫做对称二叉 B 树，从名字中可发现红黑树和 B 树（这里指的是2-3树）或许有一定的关联，事实也正是如此。

各种操作

旋转

插入

删除