二叉查找树（BST）

binary search tree

1.左子树上所有结点的值均小于或等于它的根结点的值。

2.右子树上所有结点的值均大于或等于它的根结点的值。

3.左、右子树也分别为二叉排序树。

  

 

  
1
  
2
  
3
  
4
  
5
 

红黑树

red black tree ,自平衡二叉查找树

1.节点是红色或黑色。

2.根节点是黑色。

3.每个叶子节点都是黑色的空节点（NIL节点）。

4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

红黑树的操作：

- 变色
- 旋转 - 左旋转 - 右旋转

  

 

  
1
  
2
  
3
  
4
 

参考：

1. 漫画算法：什么是红黑树？

文章来源: pengshiyu.blog.csdn.net，作者：彭世瑜，版权归原作者所有，如需转载，请联系作者。

原文链接：pengshiyu.blog.csdn.net/article/details/80203685