红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为“O(logn)”。

红黑树是在1972年由Rudolf Bayer（鲁道夫·拜尔(Rudolf Bayer, 1939-)计算机学家，慕尼黑工业大学教授）发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被Leo J.Guibas和Robert Sedgewick修改为如今的“红黑树”。
红黑树的本质就是在节点上追加了一个表示颜色的操作信息而已。

红黑树特点（规则）
1、任意一个节点不是黑色就是红色；
2、根节点必须是黑色；
3、每个叶子节点必须是黑色；

• Java实现的红黑树将使用null来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的；

4、如果一个节点时红色的，则它的子节点必须是黑色的，黑色节点的子节点可以为黑色；

• 从每个根到节点的路径上不会有两个连续的红色节点，但黑色节点是可以连续的。若给定黑色节点的个数N，最短路径情况是连续的N个黑色，树的高度为N-1；最长路径的情况为节点红黑相间，树的高度为2(N-1)；

5、从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点数量；

• 成为红黑树最主要的条件，后续的插入、删除操作都是为了遵守这个规定；

红黑树的结构就是为了可以进行左旋和右旋控制以保证树的平衡性。
数据插入平衡修复
1、新增节点颜色初始默认为红色；
2、第一次插入，由于原树为空，所以只会违反红黑树的规则2，所以只要把根节点变为黑色即可；
3、插入节点的父节点是黑色的，那不会违背红黑树的规则，不需要变色；
4、插入节点的父节点和其叔叔节点（祖父节点的另一个子节点）均为红色的，则父节点和叔叔节点都需要变为黑色，祖父节点要变为红色；
5、插入节点的父节点是红色，叔叔节点时黑色，且插入节点是其父节点的左子节点，则将父节点和祖父节点颜色互换，随后将祖父节点修改为父节点的右子节点（右旋）；
6、插入节点的父节点是红色，叔叔节点时黑色，且插入节点是其父节点的右子节点，则将父节点设置为的左子节点，插入节点将代替父节点的原始节点位置（左旋），然后使用规则4完成插入修复。
数据删除平衡修复
1、删除操作后，如果当前节点（删除后重新保存的节点）是黑色的根节点，则无法操作；
2、如果当前节点为红色的，则标明刚刚移动的后继节点是黑色的，不管后继节点的父节点是什么颜色，只要将当前节点变黑即可；
3、当前节点是黑色的，且兄弟节点是红色的（父节点和兄弟节点的子节点肯定为黑色的）；
4、当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的两个子节点均为黑色的；
5、当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的左子节点是红色的，右子节点是黑色的；
6、当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的右子节点是红色的，左子节点是任意颜色；

|参考资料|

[1] 阿里云大学Java视频课程