平衡二叉搜索树
1. 树的概念
image
一个树由节点组成，这些节点包含根节点，父节点，子节点，兄弟节点；没有任何一个节点的树称为空树；如果一棵树只包含一个节点，那么该节点为根节点；
- 节点的度（degree）: 子树的个数
- 树的度： 所有节点度中的最大值
- 叶子节点： 度为0的节点
- 非叶子节点： 度不为0的节点
- 层数（level）: 根节点在第1层，根节点的子节点在第2层，以此类推
- 节点的深度（depth）: 从根节点到当前节点的唯一路径的节点总数
- 树的深度： 所有节点深度的最大值
- 节点的高度：从当前节点到最远叶节点的路径节点总数
- 树的高度：所有节点高度中的最大值
- 树的深度等于树的高度
二叉树是每个节点的度最大为2的树，分别为 左子树 或 右子树；树按类型分为 有序树 和 无序树，二叉树是一种有序树。二叉树特征：
二叉树
- 非空二叉树的第 i 层，最多包含由
个节点，其中i >= 1;
- 高度为h的二叉树上，最多包含
- 1 个节点，其中h >= 1;
- 对于任何一颗非空二叉树，如果叶子节点个数为n0，度为2的节点个数为n2，则n0 = n2 + 1;
- 假设节点度为1的个数是n1，那么二叉树的总节点树n = n0 + n1 + n2；
- 二叉树的边数 boundary = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1；
- 可得出 n0 = n2 + 1;
二叉树分类：
-
真二叉树 是度为0，或度为2
-
满二叉树 是度为0，或度为2，且所有的叶子节点都是最后一层；满二叉树肯定是真二叉树，而且是相同层数的二叉树中节点个数最多的。
满二叉树
- 完全二叉树 是指 叶子节点只会出现在最后两层，而且最后一层的叶子节点都是向左对齐的。完全二叉树从根节点到倒数第二层都是满二叉树。完全二叉树的特效如下：
- 度为1 的节点只有左节点。 且度为1的节点数只有1个或0个；
- 同样的节点数的二叉树，完全二叉树的高度最小；
- 假设完全二叉树的高度为h (h >= 1), 那么有
- 至少有
个节点；
- 最多有
- 1 个节点；
- 节点数为
- h-1 <=
< h ；
- h = floor(
- 如果有n 节点的完全二叉树(n>0)，从上到下，从左到右的节点排序索引从1开始，对于任意的第i个节点；
- i = 1 , 表示根节点；
- i > 1 ，则父节点索引为floor(i/2)；
- 如果 2i <= n， 它的左子树索引为 2i ；
- 如果 2*i > n ，该节点无左子树；
- 如果 2i + 1 <= n ,该节点的右子节点索引为 2i + 1;
- 如果 2*i + 1 > n，该节点无右子节点；
2. 二叉树的遍历
二叉树的遍历分为 前序遍历（Preorder Traversal），中序遍历（Inorder Traversal）， 后序遍历（Postorder Traversal），层序遍历（Level Traversal）。
- 前序遍历： 从根节点, 前序遍历左子树，前序遍历右子树。遍历顺序为：4，2，1，3，6，5，7；
- 中序遍历：中序遍历左子树、根节点、中序遍历右子树。遍历顺序为：1，2，3，4，5，6，7；
- 后序遍历：后序遍历左子树、后序遍历右子树、根节点。遍历顺序为：1，3，2，5，7，6，4；
- 层序遍历：从上到下，从左到右依次访问每个节点。遍历顺序为：4，2，6，1，3，5，7；
层序遍历的应用：
- 计算二叉树的高度：
public int height() {
if (root == null) return 0;
// 树的高度
int height = 0;
// 存储着每一层的元素数量
int levelSize = 1;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
levelSize--;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (levelSize == 0) { // 意味着即将要访问下一层
levelSize = queue.size();
height++;
}
}
return height;
}
// 方式2
private int height(Node<E> node) {
if (node == null) return 0;
return 1 + Math.max(height(node.left), height(node.right));
}
- 判断是否为完全二叉树：
public boolean isComplete() {
if (root == null) return false;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
boolean leaf = false;
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
if (leaf && !node.isLeaf()) return false;
if (node.left != null) {
queue.offer(node.left);
} else if (node.right != null) { // node.left == null && node.right != null
return false;
}
if (node.right != null) {
queue.offer(node.right);
} else { // node.right == null
leaf = true;
}
}
return true;
}
前驱节点与后继节点
- 前驱节点（predecessor）：中序遍历时的前一个节点。即node.left.right.right.right...，直到right为null;
- 后继节点（successor）：中序遍历时的后一个节点。即node.right.left.left.left...，直到left为null;
3. 二叉搜索树
二叉搜索树是二叉树的一种，又被称为二叉查找树、二叉排序树。英文缩写为BST。
- 任意一个节点的值大于其左子树所有节点的值；
- 任意一个节点的值小于其右子树所有节点的值；
- 二叉搜索树节点的值必须具备可比较性。比如int， float, 如果是 自定义的对象 必须指明比较方式；
- 二叉搜索树的搜索、删除、添加最坏时间复杂度均可优化为O(logn)；
- 不允许为null；
4. 平横二叉搜索树
时间复杂度分析
上图为二叉搜索树的时间复杂度，当n较大时两者的差异比较明显。所以为了保障二叉搜索树的性能，需要保障左右子树的平衡。
平衡：当节点数量固定时，左右子树的高度越接近，这颗树就越平衡，即树的高度越低。最理想的平衡像完全二叉树、满二叉树，高度达到最小。
改进二叉搜索树的方式是在节点的添加，删除操作之后，想办法让二叉搜索树达到平衡，从而达到一颗适度平衡的二叉搜索树，称为平衡二叉树。
平衡二叉树 英文简称BBST，常见的典型平衡二叉树有：
- AVL， Window NT内核中广泛使用；
- 红黑树， java的TreeMap, TreeSet, HashMap, HashSet等广泛使用。
5. AVL
- 平衡因子（Balance Factor）指 某个节点 左右子树的高度差；
- AVL 特点：
- 每个节点的平衡因子只能为-1、0、1；
- 搜索，添加，删除的时间复杂度为O(logn)；
- 添加节点导致的失衡以及解决办法：
-
向AVL树中添加节点时（只会在叶子节点添加），可能会导致所有祖先节点都失衡，但是父节点、非祖父节点都是不可能失衡的。
-
LL ----- 右旋转
右旋转
-
RR ----- 左旋转
左旋转
-
LR ----- LR 旋转
LR旋转
-
RL ----- RL旋转: 与LR 旋转相似，先将p右旋转，再将g左旋转；略...
添加节点后，调整平衡
- 删除节点导致的失衡以及解决办法：
- 可能会导致 父节点 或 祖先节点 失衡（只有1个节点失衡），其他节点不会导致失衡。恢复平衡后，可能会导致更高层的祖先节点失衡。删除和添加的都是根据节点所在的位置是否失衡，来进行旋转，以达到平衡。
-
一直递归父节点以及祖父节点，先判断平衡因子是否-1，0，1，如果不是调整节点的平衡(rebalance)
删除后，调整平衡
- 平均时间复杂度
- 搜索：O(logn)；
- 添加：O(logn)，仅需O(1)次旋转操作;
- 删除：O(logn)，最多需要O(logn)次旋转操作；
6. 红黑树
红黑树
红黑树也是一种自平衡的二叉搜索树，红黑树的5个特性：
- 节点是 Red 或者 Black；
- 根节点是 Black；
- 叶子节点（外部节点、空节点）为 Black；
- Red 的子节点都是 Black节点（即在所有路径上，不可能包含连续2个为 Red 的节点）；
- 任意节点 到 叶子节点的所有路径上包含相同数量的 Black 节点；
红黑树 和 4阶B树具有等价转化。
- Black 节点与它的 Red 子节点融合形成B树的一个节点；
- 红黑树的 Black 节点个数 与 4阶B树的节点总数相等；
1） 添加 节点：
parent : 父节点
sibling : 兄弟节点
uncle : 叔父节点（parent节点的兄弟节点）
grand : 祖父节点 （parent节点的父节点）
新添加的节点必须添加到叶子节点中，建议新添加的为 Red 节点，这样可以尽可能满足红黑树性质，即满足性质1，2，3，5，性质4不一定满足。
- 如果添加的是根节点，那么直接染成 Black；
- 如果 parent 节点是 Black，那么添加的 Red 节点不需要做任何处理，就已经符合红黑树的全部性质；
88节点的添加
- 如果 parent 节点是 Red，就会出现连续两个 Red，不符合性质4，需要进行处理；
a. 如果 uncle 节点不是 Red，将会导致节点上溢；
b. 如果 uncle 节点不是 Red，添加节点的位置 LL \ RR；
1）将 parent 染成 Black，将 grand 染成 Red；
2）对 grand 进行单旋转操作；
uncle节点不是red，LL\RR情况
c. 如果 uncle 节点不是 Red, 添加节点的位置 LR \ RL；
1）将自己染成 Black，将 grand 染成 Red；
2）进行 LR\RL 双旋转；
uncle节点不是red，LR\RL情况
d. 如果 uncle 节点是 Red；
1）将 parent，uncle 染成Black；
2）将 grand 染成 Red，向上合并，即当作新的节点进行处理；
uncle节点是red，将parent、uncle染成black，grand染成red，向上合并当作新节点添加
2） 删除 节点：
由于删除节点时，我们会使用B树的前驱或后继节点来替换该节点，实际上删除都是叶子节点
-
删除的是 Red 节点，不需要任何处理；
-
不可能直接删除拥有2个Red 子节点的 Black 节点，因为这个节点会找到前驱或后继节点来替换，所以不考虑；
-
所以只需要考虑， 删除的是拥有 1个Red 子节点的 Black 节点 或者 Black的叶子节点:
-
删除的是拥有 1个Red 子节点的 Black 节点：
a. 用 Red子节点替代 parent节点；
b. 将替代的Red 子节点染成 Black，既可以修复红黑树性质； -
删除Black的叶子节点，并且sibling为Black；
a. 如果sibling最少有一个Red 子节点：
1）根据情况，进行之前的LL、RR、LR、RL旋转
2）旋转后，中心点（该子树的根节点）继承parent的颜色；
3）旋转后，将左右子节点染成 Black；
删除Black的叶子节点，并且sibling为Black（80）
b. sibling没有一个Red 子节点：
1）将sibling 染成 Red, parent 染成 Black，就可以修复红黑树性质；
删除Black的叶子节点，sibling没有一个**Red** 子节点
- 删除Black的叶子节点，并且sibling为 Red；
a. 先将sibling染成 Black，parent 染成 Red，在进行旋转操作；
b. 回到sibling 是 Black的情况，再进行删除操作；
删除**Black**的叶子节点，并且sibling为 **Red**
3） 红黑树的平均时间复杂度：
- 搜索：O(logn)；
- 添加：O(logn)，O(1)次旋转；
- 删除：O(logn)，O(1)次旋转；
4） AVL 与 红黑树对比：
-
AVL 标准比较严格，平衡因子不能超过1；
-
AVL的树高度 比 红黑树高度低；
-
AVL搜索，添加，删除的时间复杂度都是O(logn)，添加仅需O(1)次旋转调整，删除最多需要O(logn)次旋转操作；
-
红黑树 的搜索，添加，删除操作时间复杂度都是O(logn)，添加和删除仅需O(1)次旋转调整；
-
搜索的次数远远大于添加，删除时，优先选择AVL（高度比较低），否则选择红黑树，总体上红黑树的性能 比 AVL高；
绘图工具： BinaryTreeGraph；
