treemap

Ordered Map written in Go, based on RB-Tree.

0 QuickStart

1 Features

• 性质1：每个节点是 黑色 or 红色；
• 性质2：根节点是黑色；
• 性质3：每个叶子节点（NIL）是黑色；
• 性质4：每个红色节点的两个子节点一定都是黑色；
• 性质5：任意一节点到每个叶子节点的路径都包含数量相同的黑节点。

由性质5:

• 性质5.1：如果一个节点存在黑子节点，那么该节点肯定有两个子节点

---

一些定义：

• 左旋：以某个节点作为支点(旋转节点)，其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变。（参考后面示例）
• 右旋：以某个节点作为支点(旋转节点)，其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变。
• 变色：节点的颜色由红变黑或由黑变红。

2 Operation

2.1 查找

等同二叉树查找

2.2 插入

2.2.1 根节点不存在

设置为根以及黑色即可

2.2.2 插入key已存在

更新值即可，保留颜色和原有数据结构

2.2.3 插入key不存在

新节点默认为红色，且易知新节点均在叶子节点（原 Nil 节点）。

假定当前节点为新加入的节点，有以下几种情况

1. 父节点为黑色

直接插入即可

2. 父节点为红色

易知父节点不为根，即新节点必定存在祖先节点。**且祖先节点为黑色**
新节点和父节点连续两个红节点，需从新节点开始进行调整。

# 2.1 叔节点存在且为红
则将父和叔设置为黑 祖父为红 重新调整祖父节点即可
【即将祖父的黑色向下降级】

# 2.2 叔节点不存在或为黑 并且父节点是祖节点的左子节点
## 2.2.1 新节点是父节点的左子节点：祖父右旋 层颜色不变
       pp(黑)                          p(黑)
    p(红)              =>           x(红)   pp(红)
 x(红)
 
## 2.2.2 新节点是父节点的右子节点：父左旋 祖父右旋 层颜色不变
       pp(黑)               pp(黑)            x(黑)
    p(红)        =>       x(红)       =>   p(红)    pp(红)
         x(红)         p(红)
【其实就是减少层数的同时维护大小关系】

# 2.3 叔节点不存在或为黑 并且父节点是祖节点的右子节点
## 2.3.1 新节点是父节点的右子节点：祖父左旋 层颜色不变
## 2.3.2 新节点是父节点的左子节点：父右旋 祖父左旋 层颜色不变
略

若祖父不存在直接把根置黑即可

2.3 删除

2.3.1 待删除节点不存在

直接返回

2.3.2 待删除节点存在

以下替换均为值替换，不会破坏黑高。

1. 删除节点无子节点

直接结束

2. 待删除节点只有一个子节点

用子节点替换删除节点

3. 待删除节点有两个子节点 用后继节点（大于删除节点的最小节点 右子树的最左节点 若右子树不存在则在父存在且当前节点为父节点的右子节点时保持循环(即父节点不存在则是nullptr 否则在是父节点的左子节点时返回父节点)）替换删除节点

删除节点被替代后，在不考虑节点的键值的情况下，对于树来说，可以认为删除的是替代节点

2：子节点替换为删除节点后，可以认为删除的是子节点。若子节点又有两个子节点，那么相当于转换为3，最终转化为1

3：后继节点有右子节点【注意此时后继节点肯定不存在左节点或左节点即为被删除节点所在的分支】，相当于转换为2，否则转为1

# 3.1 替换节点为红
替换节点的颜色设置为被删除节点的颜色即可
（因为替换节点从其位置上消失不影响原树的平衡性）

# 3.2 替换节点为黑
## 3.2.1 替换节点是其父的左
### 3.2.1.1 兄弟是红
则父和兄弟子为黑
兄弟变黑父变红 对父左旋
### 3.2.1.2 兄弟是黑
父节点和子节点颜色无法确定
#### 3.2.1.2.1 兄弟右是红 左任意
即将删除左子树的一个黑色节点 显然左子树黑色节点少一 而右红 直接向右“借”一个红来补充左子树黑色节点
兄弟设置为父的颜色 兄弟右变黑 父变黑 对父左旋
#### 3.2.1.2.2 兄弟右是黑 左红
可以转化为 3.2.1.2.1
兄弟变红 兄弟左变黑 对兄弟右旋
#### 3.2.1.2.3 兄弟右 左 都黑
兄弟设置为红 父作为新的删除节点
## 3.2.2 替换节点是其父的右
### 3.2.2.1 兄弟是红
### 3.2.2.2 兄弟是黑
#### 3.2.2.2.1 兄弟左红 右任意
#### 3.2.2.2.2 兄弟左黑 右红
#### 3.2.2.2.3 兄弟左右 都黑
略