二叉排序树

又叫二叉搜索树BST

对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值
BST的所有子树都是BST.

普通排序树

查找结点

查找
/* 查找节点 */
TreeNode *search(TreeNode *root, int num) {
    TreeNode *node = root;
    // 循环查找，越过叶节点后跳出
    while (node != nullptr) {
        // 目标节点在 node 的右子树中
        if (node->val < num)
            node = node->right;
        // 目标节点在 node 的左子树中
        else if (node->val > num)
            node = node->left;
        // 找到目标节点，跳出循环
        else
            break;
    }
    // 返回目标节点
    return node;
}

插入结点

二叉搜索树不允许存在重复节点，否则将违反其定义。因此，若待插入节点在树中已存在，则不执行插入，直接返回。

删除结点

先搜索找到目标结点：

若是被删除的结点z是叶节点，则直接删除，不会破坏二叉排序树的性质。
若结点z只有一棵左子树或右子树，则让z的子树称为z父节点的子树，替代z的位置
若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。

二叉排序树的中序遍历有序: 其中在寻找直接前驱和直接后继时进行中序遍历，可以得到一个递增的有序序列。

用右子树最小的值来替代被删除的值（最左下）

相似继承算法

被删除节点的直接前驱或直接后继代替被删除节点，然后删除被删除节点的直接前驱或直接后继。

delete the node
int delete(int num){
  search(num) -> val = nearestNode(search(num)) --> val;
  nearestNode
}

数组与搜索树的效率对比

	无序数组	二叉搜索树
查找元素	$O(n)$	$O(\log n)$
插入元素	$O(1)$	$O(\log n)$
删除元素	$O(n)$	$O(\log n)$

平衡二叉树AVL

平衡因子：左高度-右高度

平衡二叉树是平衡因子的绝对值不大于1的二叉排序树。

旋转

旋转操作是多数平衡树能够维持平衡的关键，它能在不改变一棵合法 BST 中序遍历结果的情况下改变局部节点的深度。

插入

我称之为中间派贿赂算法。

顾名思义，一但插入破坏了平衡，那么政局就倒向了势力大的一方，但最好的结局就是选择一个中间派（需要找到失衡点和它的子树）。

自底向上执行旋转操作，使所有失衡节点恢复平衡。

删除

删除过程：相似继承算法（执行BST的删除操作）
平衡过程：中间派贿赂算法 + 回溯（AVL平衡需要）

红黑树RBT

自平衡的二叉搜索树，每个节点额外存储了一个 color 字段 ("RED" or "BLACK")，用于确保树在插入和删除时保持平衡。

特点：

节点为红色或者黑色
端节点（没有信息）为黑色
红色不能连接红色
从根节点到端节点的每条路径都具有相同数量的黑色节点

定义
template <typename Key, typename Value, typename Compare = std::less<Key>>
class RBTreeMap {
  // 排序函数
  Compare compare = Compare();

  // 节点结构体
  struct Node {
    ...
  };

  // 根节点指针
  Node* root = nullptr;
  // 记录红黑树中当前的节点个数
  size_t count = 0;
};

Identifier	Type	Description
left	`Node *`	左子节点指针
right	`Node *`	右子节点指针
parent	`Node *`	父节点指针
color	`enum { BLACK, RED }`	颜色枚举
key	`Key`	节点键值，具有唯一性和可排序性
value	`Value`	节点内储存的值

注意

由于红黑树是由 B 树衍生而来（发明时的最初的名字 symmetric binary B-tree 足以证明这点），并非直接由平衡二叉树外加限制条件推导而来，插入操作的后续维护和删除操作的后续维护中部分对操作的解释作用仅是帮助理解，并不能将其作为该操作的原理推导和证明。

插入

由于该部分旋转操作case太多，所以为了简单应对，创造了一个模型去辅助操作。我把它命名为民主革命算法。

两党民主算法：整个红黑树代表政坛。一个节点代表一个人物。人物分两种：红色（在野党/没有话语权），黑色（执政党/拥有话语权）。总统：根节点。同僚：你的兄弟节点。上层领导：你的最近的黑色节点。上层部门：你的上层和他的同僚，即高层的下属。下属：子节点。你：最为三级最下层的一级。副总统：老板的两个子节点。高层：上层的上层。

首先有几个需要明确的：

你只能通过在野党的身份进入政坛。（这可能是某种规定）
在野党不能太近（直接连接），否则在野党力量太集中，就会反抗上台，甚至整个政坛动荡。

我们现在假设你是在野党（我们只是以你为中心分析。其实如果你是执政党阵营，那政坛是稳定的，不会发生动荡），有几种情况：

你的上层是执政党，那么你的在野党身份就不会有翻身的机会。（你如果是副总统，那总统一定是执政党。因为不存在执政党既不是总统也不是副总统的情况。）
如果你的上层是在野党，那么：
1. 你的上层部门都是在野党，那高层直接被架空（转红），你的上层领导可以直接夺权。（转黑）（需要递归维护上层部门）
2. 如果你的上层部门分属两党，那么你和你的领导中距离高层近的人，被选举上位执政，原高层下台。

二叉排序树

普通排序树​

查找结点​

插入结点​

删除结点​

平衡二叉树AVL​

插入​

删除​

红黑树RBT​

插入​