19. 数据结构之红黑树

定义

红黑树是一棵自平衡二叉树.

性质

（1）每个节点或者是黑色，或者是红色。 
（2）根节点是黑色。 
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！] 
（4）如果一个节点是红色的，则它的子节点必须是黑色的。 
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

注意：
(01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。
(02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

image.png

应用

红黑树广泛的应用在各种程序库中，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。在linux内核的进行调度上面，C++中stl中的很多容器多采用了红黑树的算法，Java中的TreeMap也是采用了红黑树的算法来实现排序。

基本操作

旋转

红黑树的旋转相比二叉平衡树，要简单一点，因为其只有两种旋转操作，即左旋和右旋。
1. 左旋

是不是感觉上面的左旋很熟悉，其实就是平衡二叉树中的右右的这种情况，
用 x 右节点代替 x，其右节点的右子树保持不变，并且将其右节点的左子树赋给 x 的右子树，完毕。

2. 右旋

与左旋完全相反，用 y 左节点代替 y，其左节点的左子树保持不变，并且将其左节点的右子树赋给 y 的左子树，完毕。
    如何区分右旋 左旋 
    这是一个问题，但是仔细观察上面，就是左旋就是让旋转的节点变成左子树，右旋就是让旋转的节点变成右子树，
简单的总结一句话，
    左旋–>提右节点，变左子树
    右旋–>提左节点，变右子树

欢迎关注，以后会不定时更新！

摘自网上