DS binary tree (4)

# 【資工考研】DS: Binary Tree (4) AVL Tree + B Tree of Order m ## AVL Tree 我們在[介紹 BST 時](https://hackmd.io/@RyoukiWei/binary_tree_1?stext=23016%3A113%3A0%3A1737374008%3A1_UqSU)說過，BST 之所以 worst case 的時間複雜度會退化成線性跟其高度未平衡有關係 AVL Tree 是 height balanced BST 定義 $H_L$ 跟 $H_R$ 分別為左右子樹的高度，當樹不為空時滿足： 1. $\left| H_L - H_R \right| \le 1$ 2. 左右子樹亦為 AVL Tree AVL tree 控制高度平衡的機制仰賴的便是 balance factor： $H_L - H_R$ 其值只會是 $-1,0,1$ 透過 balance factor 我們便能在高度不平衡時立刻發現，然後調整每當我們插入一個新節點，如果會造成不平衡，則依據該新節點位在往左子樹還是往右子樹的方向插，我們可以分成四種情況討論： ![image](https://hackmd.io/_uploads/ByY662iv1g.png) AVL tree 的調整仰賴 rotation 的動作，可以分成 right roation 跟 left rotation 以下面這種情況來說： ![image](https://hackmd.io/_uploads/HytqC3jPkx.png) 這個大中小的相對比較是因為 BST 的規則 AVL tree 肯定也是要遵守的我們要如何對此 right roation 呢？想像樹節點就像鍊條一樣，我們擺一個三角形台子，right rotation 其實也就是把大中小這一串抓住最上面的節點，把他往右拉節點會順著三角形台子移動： ![image](https://hackmd.io/_uploads/ByVpl6iDJx.png) 這邊的 $t$ 根據 BST 性質，$t \gt x$ 所以當 $x$ 的左右子樹變更時，$t$ 應該會是在 $x$ 的右子樹又 $t \lt y$ ，所以 $t$ 會在 $y$ 的左子樹 left rotation 也是類似的樣子前面我們討論的 LL 跟 RR 只需要這樣的 rotation 一次即可例如 LL 只需要 single right rotation 而 LR 跟 RL 則需要 double rotation 例如 LR 要先抓新節點的父輩做 left rotation ，這樣新節點才會變成 LL 的樣子，這時再 right rotation 即可輔助的 method ： ```cpp! int getHeight(Node *node) const noexcept { return node ? node->height : 0; } int getBalanceFactor(Node *node) const noexcept { return node ? getHeight(node->left) - getHeight(node->right) : 0; } Node *findMin(Node *node) noexcept { if (!node) return node; Node *curr = node; while (curr->left) curr = curr->left; return curr; } void updateHeight(Node *node) const noexcept { node->height = std::max(getHeight(node->left), getHeight(node->right)) + 1; } ``` ### rotation ```cpp! Node *rightRotate(Node *y) { // x will become the new root of the subtree Node *x = y->left; Node *t = x->right; // Rotation x->right = y; y->left = t; updateHeight(y); updateHeight(x); return x; } Node *leftRotate(Node *x) { // y will become the new root of the subtree Node *y = x->right; Node *t = y->left; // Rotation y->left = x; x->right = t; updateHeight(x); updateHeight(y); return y; } ``` ### Insert ```cpp! std::pair<Node *, bool> insertUtil(Node *node, const T &val) { if (!node) return {new Node(val), true}; if (val == node->data) return {node, false}; if (val < node->data) node->left = insertUtil(node->left, val).first; else node->right = insertUtil(node->right, val).first; updateHeight(node); const int bf = getBalanceFactor(node); if (bf > 1 && val != node->left->data) { // if LR else LL if (val > node->left->data) node->left = leftRotate(node->left); return {rightRotate(node), true}; } if (bf < -1 && val != node->right->data) { // if RR else RL if (val < node->right->data) node->right = rightRotate(node->right); return {leftRotate(node), true}; } return {node, true}; } ``` 可以看到 LR 跟 RL 需要額外檢查跟一次 rotation 分別變成 LL 跟 RR 後再一次 rotation ### erase ```cpp! Node *eraseUtil(Node *node, const T &val) { if (!node) return node; if (val < node->data) node->left = eraseUtil(node->left, val); else if (val > node->data) node->right = eraseUtil(node->right, val); else { if (!node->left && !node->right) { Node *temp = node; node = nullptr; delete temp; } else if (!node->left || !node->right) { Node *temp = node->left ? node->left : node->right; *node = *temp; delete temp; } else { Node *successor = findMin(node->right); node->data = successor->data; node->right = eraseUtil(node->right, successor->data); } } if (!node) return node; updateHeight(node); const int bf = getBalanceFactor(node); if (bf > 1) { if (getBalanceFactor(node->left) < 0) node->left = leftRotate(node->left); return rightRotate(node); } if (bf < -1) { if (getBalanceFactor(node->right) > 0) node->right = rightRotate(node->right); return leftRotate(node); } return node; } ``` ### 重要性質對 AVL tree ： - `insert()` 頂多發生 $O(1)$ 次 rotation - `erase()` 頂多發生 $O(\lg n)$ 次 rotation - 形成高度 $h$ 的 AVL tree (root level $=1$) 所需的 - 最多節點數： $2^h-1$ - 最少節點數： $F_{h+2}-1$ 其中 $F_n$ 是費氏數 (可以用數學歸納法證) 因為 $\left| F_h \right| + 1\approx \frac{1}{\sqrt 5}(\frac{1 + \sqrt 5}{2})^{h+3}$ (離散的老朋友費氏數列，遞迴式會解吧？) 所以對於 $n$ 個節點的 AVL tree ， $h\approx 1.44\lg n$ 也就是說 AVL tree 樹高的 worst case 的確還是 $O(\lg n)$ 沒錯 ## B Tree of Order m - Balanced m-way search tree - 若非空樹，滿足： - $2 \le \mathrm{deg}(\mathrm{root})\le m$ - $\left\lceil \frac{m}{2} \right\rceil \le \mathrm{deg}(\mathrm{node})\le m, \mathrm{node}\neq\mathrm{root}$ - All external nodes must be the same level (其平衡的意義所在) ![image](https://hackmd.io/_uploads/rJjX9xavyg.png) [source](http://www.btechsmartclass.com/data_structures/b-trees.html) > [!Important] > - The max number of nodes: $\sum\limits_{i=1}^{h}m^{i-1} = \frac{m^h-1}{m-1}$ > - The min number of nodes: $1 + 2\left\lceil \frac{(\left\lceil \frac{m}{2} \right\rceil)^{h-1}-1}{\left\lceil \frac{m}{2} \right\rceil - 1} \right\rceil$ > - The max number of keys: $m^h-1$ > - The min number of keys: $2(\left\lceil \frac{m}{2} \right\rceil)^{h-1}-1$ > [!Tip] > - B tree of order 3 又叫 2-3 tree > - B tree of order 4 又叫 2-3-4 tree ### Insert (bottom up) ```pseudocode! INSERT(T, x): SEARCH(T, x) Let p ← parent of the external node where x should be inserted. INSERT-KEY(p, x) while number of keys in p > m - 1 do SPLIT(T, p) p ← parent of p ``` ```pseudocode! SPLIT(T, p): Let k ← the ⌈m / 2⌉-th key in p. Move k to the parent of p. Create two new children nodes: Left-child contains keys less than k. Right-child contains keys greater than k. Update the parent's child pointers to include the new left and right children. ``` ### Insert (top down) 在 insert x 時，search x path 若遇到 m-node ，先 split 再置入到正確的 node 內 ### Delte ``` DELETE-BTREE(T, x): SEARCH-TARGET(T, x) Let N ← the node containing x. if N is a leaf then ERASE-KEY(N, x) HANDLE-UNDERFLOW(T, N) else // N is a non-leaf node Let y ← the predecessor or successor of x (largest key in the left subtree or smallest key in the right subtree). REPLACE-KEY(N, x, y) DELETE-BTREE(T, y) ``` ``` HANDLE-UNDERFLOW(T, N): // safe if number of keys in N ≥ ⌈m / 2⌉ - 1 then return else if N has a sibling with extra keys (rotation is possible) then PERFORM-ROTATION(T, N) else // Merge is necessary PERFORM-MERGE(T, N) Let P ← parent of N. HANDLE-UNDERFLOW(T, P) ``` ``` PERFORM-ROTATION(T, N): Let S ← a sibling of N with extra keys. if S is to the left of N then Move the largest key in S to the parent of N. Move the parent's separating key to N. else // S is to the right of N Move the smallest key in S to the parent of N. Move the parent's separating key to N. ``` ``` PERFORM-MERGE(T, N): Let S ← a sibling of N. Let P ← parent of N. Merge N and S into a single node, including the separating key from P. Remove the separating key from P. ``` > [!Warning] > 如果 merge 後 parent is underflow > 要切斷所有這代父輩與其子輩們的 link ，parent 做 rotation 若真的不行再 merge > 等父輩們都搞定了再重建關係 > [!Important] > 這邊的 rotation 與 AVL tree 的不同喔 ### B+ Tree of Order m 支援 index sequential access method 主要分兩層： - index level: 使用 B tree of order m ，純粹用來做**索引**，不用來存放 data - data blocks level: 存 data 用的，各個 blocks 間以 linked list 的方式串接 ## 【資工考研】DS: Binary Tree 全系列 - [【資工考研】DS: Binary Tree (1)](https://hackmd.io/@RyoukiWei/binary_tree_1) - [【資工考研】DS: Binary Tree (2)](https://hackmd.io/@RyoukiWei/binary_tree_2) - [【資工考研】DS: Binary Tree (3)](https://hackmd.io/@RyoukiWei/binary_tree_3) - [【資工考研】DS: Binary Tree (4)](https://hackmd.io/@RyoukiWei/binary_tree_4) - [【資工考研】DS: Binary Tree (5)](https://hackmd.io/@RyoukiWei/binary_tree_5)