什么是树

树是一种数据结构，有一个根节点

每个节点包含n（n>=0）个子节点

没有子节点的节点称为叶子节点

二叉树

二叉树是每个节点最多有两个子树的树结构

通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）

二叉树常被用于实现二叉查找树和二叉堆

二叉树的节点放置规则是：任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中每一个节点的键值。因此，从根节点一直往左走，直至无左路可走，即得最小元素；从根节点一直往右走，直至无右路可走，即得最大元素。

平衡树

平衡树，即平衡二叉树（Balanced Binary Tree）

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

平衡二叉树的常用算法有红黑树、AVL、Treap、伸展树、SBT等

平衡树在每次插入或删除的时候通过左旋/右旋来不断调整根节点以达到平衡

1. 二叉左旋

一棵二叉平衡树的子树，根是Root，左子树是x，右子树的根为RootR，右子树的两个孩子树分别为RLeftChild和RRightChild。则左旋后，该子树的根为RootR，右子树为RRightChild，左子树的根为Root，Root的两个孩子树分别为x（左）和RLeftChild（右）。

2. 二叉右旋

一棵二叉平衡树的子树，根是Root，右子树是x，左子树的根为RootL，左子树的两个孩子树分别为LLeftChild和LRightChild。则右旋后，该子树的根为RootL，左子树为LLeftChild，右子树的根为Root，Root的两个孩子树分别为LRightChild（左）和x（右）。

红黑树

红黑树是一个平衡的二叉树，但不是一个完美的平衡二叉树

红黑树需要同时满足以下5个特性：

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

红黑树有什么用

红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高

转换成红黑树的目的就是为了提高查询效率

例如，Java集合中的TreeSet和TreeMap，以及jdk1.8的hashMap链表转红黑树

添加节点

红黑树也是二叉树，放置规则必须满足二叉树的规则

然后插入之后必须通过左旋/右旋/调色操作，以满足红黑树的5个特性

操作步骤

1. 将插入节点标记为红色
2. 逐步检查每个特性，如果不满足就通过左旋/右旋，以及调色操作进行调整

后续有空会增加示例代码，先简单描述一下，这5个条件的判断操作其实还挺麻烦的

删除节点

删除操作和添加类似

参考资料

• https://www.cnblogs.com/skywang12345/p/3245399.html