知识总览：

为什么要发明红黑树：

二叉排序树BST

红黑树RBT的查找、插入和删除效率基本和AVL平衡二叉树的相同，但是平衡二叉树在插入和删除节点操作时容易被破坏平衡，所以需要消耗大量时间重新调整树的形态(主要时间用在计算平衡因子，找最小不平衡树等)，而红黑树在插入和删除操作时就不需要频繁调整树的形态，即便需要调整，一般也可在常数级完成，所以红黑树很牛

一般查询多，插入删除少的用平衡二叉树，如果是插入、删除多的用红黑树

j 

红黑树定义：

红黑树是二叉排序树的一种优化，则红黑树有二叉排序树BST的特性，即节点值左子树<根节点<右子树(左<中<右) ，每个节点上除了有左子孩子指针外，还有节点的颜色color

定义：

1.红黑树的节点的颜色要么是黑色要么是红色

2.红黑树中的叶节点一般指的是查找失败的节点，叶节点又叫NULL空节点或者外部节点，注意不是最下层的节点，二叉排序树中的查找失败的节点也是NULL节点即不存在的节点，根节点和叶节点一定都是黑色的节点

4.红黑树中的父子节点不能出现连续的红节点，但是如果是兄弟节点可以是连续的红节点，如下图3，节点17是红节点，则它的父节点13和孩子节点15和25必须都是黑节点，否则就出现连续的红节点了，如果15节点是红节点，则不满足红黑树定义，22和27是兄弟节点可以是连续红节点

5.从任一节点(包括根节点)出发，该节点到任一叶节点的有各种各样的路径，但是不管是啥路径，在各个路径上所经过的黑节点的个数是相同的。如下从13出发可以到达各个叶节点，13->8->1->null,13->8->11->null,13->17->15->null等等路径，所经过的黑节点个数都是2(注意从某个节点出发所经过的黑节点数量不包括出发节点，即便是从该节点出发该节点是黑节点，那也不包括)，以上路径所经过的黑节点依次是(1,null)、(11,null)、(15,null)即都是2个黑节点

红黑树口诀：

左根右======》指的是满足节点值左子树<根节点<右子树

根叶黑======》指的是根节点和叶子节点都是黑节点

不红红======》指的是父子节点不存在2个相邻的红节点

黑路同======》指的是一条路走到黑，走到叶子节点(叶子节点是黑的)，所包含的黑节点数目相同

平衡二叉树AVL也是二叉排序树的一种优化，AVL每个节点上除了有左右孩子指针外，还有平衡因子

练习：

如下截图中分别违反不红红(父子节点2个红节点不能相邻)和根叶黑要求(根节点是黑色的)、黑路同(从1节点出发到叶子黑节点，经过的黑节点数目分别为1和2)，即不符合红黑树要求

 

补充概念：节点的黑高

黑高bh定义： 从某一节点出发(不包含该节点)到达任一空叶节点的路径上的黑节点的数目(跟上边的红黑树的黑路同特性类似)

如下15节点的bh=2，即15->11->8->null(黑节点为11和NULL节点)或者15->18->null(黑节点为18和和NULL节点)等等在到达叶节点上的路径上的黑节点的数目都是2，根节点6bh=2同，6->2->null(黑节点为2、NULL节点)或者6->15->18->20->null(黑节点为18、NULL节点)等等路径的黑节点的数目=2

 红黑树的性质：

1.从根节点到叶节点的最长路径不大于最短路径的2倍（这个是因为不允许2个红节点相邻出现，所以最长路劲肯定是红黑交叉的路径，所以最长路径不大于最短路径的2倍。。。。可能是吧。。）

2.有n个内部节点的红黑树高度h<=2log2(n+1)，即红黑树的查找效率为log2n数量级，即红黑树的查找时间复杂度为O(log2n)

红黑树的查找：因为红黑树也是二叉排序树，所以查找和二叉排序树一样，从根节点出发，左小右大，若找到空叶节点则查找失败

知识回顾：

 

又水一篇。。。。。。。。。。。。。