# 树
Binary Tree
Complete Binary Tree
Perfect Binary Tree
Binary Search Tree(BST)
Threaded Binary Tree(Preorder, Inorder, Postorder)
AVL Tree

Traversals
* Preorder
* Inorder
* Postorder


**Binary Search Tree**
* Insertion
    * 比，将要插入的节点与BST中的节点进行比较
    * 插入，将新节点插入到比较到最后一层的叶子节点之下
* Deletion
    * 直接删除叶子节点
    * 要删除的节点只有一个孩子节点，replacement node就是这个孩子节点
    * 以上两种情况无法使用，replacement node需要满足：
        * 比要删除节点的左子树中的任何一个节点都大
        * 比要删除节点的右子树中的任何一个节点都小
        找replacement node的方法：
        1. make a hole，将要删除的节点先移走，产生一个空洞
        2. 从这个空洞向左移动一次，然后尽可能向右移动 或 从这个空洞向右移动一次，然后尽可能向左移动
        3. 找到replacement node后，再次make a hole然后继续处理

BST Height (n nodes)
1. 最坏的情况是BST退化成链表，$ h = n -1$
2. 最好的情况是BST的高度想要越小，则BST越接近满二叉树，$ h = \lceil \log(n + 1) -1\rceil$
3. 平均的情况，n个节点可以有$n!$种排列（permutation），计算平均高度，$h \approx O(\log(n))$

**AVL Tree**
左右子树的高度差不超过1
Rotation 
* Left rotation
* right rotation 
* Left-Right rotation
    A left rotation on a left child followed by a right rotation on the parent
* Right-Left rotation
    A right rotation on a right child followed by a left rotation on the parent

n nodes, $h = O(\log(n))$

**2-3 Tree**
2/3 children
1/2 keys
一个节点是2 nodes代表它有两个children，只有一个key
一个节点是3 nodes代表它有三个chilren，有两个keys


**B Tree**(multiway search tree)
根节点有$1\sim m-1$个keys，$2 \sim m$个children
非根节点有$\lceil m/2 \rceil-1 \sim m-1$个keys，$\lceil m/2 \rceil \sim m$个children
m, k keys, h height 
$h = O(\log(k)), h \leqslant \log_{\lceil m/2\rceil}(\frac{k+1}{2})$
**Tree Restructuring**
Overfull / Underfull
满载/不足
1. Rotation（插入遇到满载或删除遇到不足时使用）
    一个节点满载，而它右边的兄弟节点有空间时：将这个节点的最大的key给升级promote，作为parent key，将原来的parent key给降级demote到右边的兄弟节点，作为这个节点的最小的key，将左边这个满载节点原来最大的孩子移动到右边兄弟节点，作为最小的孩子![](</document-assets/data-structure-tree/85b2d2b86bc84f1cf91d89f95bf738930dad2fa4274848de7813e156c7a9bcf7.png>)

2. Splitting（插入遇到满载时使用）
![](</document-assets/data-structure-tree/7c1437b0fbd00055e186f2f880babf61034e5611cd403bf50f797243d768f5c4.png>)

3. Merging（删除遇到不足时使用）
![](</document-assets/data-structure-tree/c8b77bb9085d5d862818255bb3d297db9c34455a5f74a2815dc938ac91c96c64.png>)


**B+ Tree**
B+树是B-树的变体
* B+树内部节点只储存keys而不储存values（实际的数据）
* 所有的键值对都被储存在叶子节点
*  每一个叶子节点都有一个指向它右边叶子节点的

B+ 树中所有的 key 必须出现在叶子节点，而内部节点的 key 只是这些叶子节点 key 的副本，用于索引和导航。
![Screenshot 2025-09-08 at 17.14.46](</document-assets/data-structure-tree/f5d7c90a50493b711c7b83422e2a5d45c3cec23a8bfa52c122d9f564ff0526b5.png>)


**Red-Black Tree**（BST）
1. 每个节点要么是红色的，要么是黑色的
2. 根节点是黑色的
3. 如果一个节点是红的，它的两个孩子节点是黑色的
4. 所有的空指针要被看作指向黑色节点
5. 从指定节点到其的任何一个空子节点的每条路径包含了同等数量的黑色节点

节点的层级（Black-height）
* 最低的黑色节点是level 1
* 从下往上，黑色节点的层级也在变大
* 红色节点的层级等于它的父节点的层级
* 最低的节点，有着空子节点，这些空子节点是level 0
![](</document-assets/data-structure-tree/1f24f07f993013319c0b13297a47e4cf392508b9a5e5723323ef1196eb81b25e.png>)

红黑树的高度（黑高）是根节点层级与叶子节点层级的差值
$\log(n+1) \leqslant h \leqslant 2\log(n+1)$


**AA Tree** (Red-Black Tree)
新增加一个条件，将红黑树变为AA树：
每一个红色节点只能作为一个黑节点的右孩子出现

AA树只有三中平衡操作（Balancing Operations）
* skew(iff Right Rotate)
 The skew operation fixes the existence of a red left child
 Skew操作修复左孩子红色节点问题
![](</document-assets/data-structure-tree/5c8858fc5aa5a1b992e7b80d970cc947fd14a5b6c85f506d93b44e7ab70fb6df.png>)

* split(iff Left Rotate)
The split operation fixes the existence of a red child of a red child. 
Split操作修复了一个红色孩子节点的还有红色孩子节点的问题
* update-level(只用于删除)
update-level checks to see if the node is more than one level higher than its lowest child
update-level操作检查了这个节点的层级是否比它的最低孩子节点的层级大1