# 【資工考研】DS: Binary Tree (1) Binary Tree + Binary Search Tree + Heap
## Tree Basic Definition
- 不可為空 (node 數 $\gt 0$)
- 至少一個特定節點稱為 root
- 其餘的節點可分為 $k$ 個集合 ($T_1,T_2,\cdots ,T_k$) 稱為 subtree of a root
- subtree 本身沒有方向性
## Tree Representations
1. linked list
2. transform into the binary tree
3. child-sibling
4. parentheses
如何表示一棵樹呢？有上述四種方法，不過這邊我們只細談第一種
假設有下面這棵樹：
```graphviz
graph linked_list{
rankdir=TD;
graph [fontname="DFKai-SB"];
node [fontname="DFKai-SB"];
edge [fontname="DFKai-SB"];
label="Use the Linked List to Represent a Tree"
{rank=same A}
{rank=same B C D}
{rank=same E F}
A--B
A--C
A--D
C--E
C--F
}
```
我們可以這樣表示樹的節點，然後連接節點
```graphviz
digraph structure {
rankdir=TD;
graph [fontname="DFKai-SB"];
node [fontname="DFKai-SB" shape=record, width=1.2, height=0.6];
edge [fontname="DFKai-SB"];
A [label="{ <data> A | <ref1> | <ref2> | <ref3> | <ref4> }"];
B [label="{ <data> B | <ref1> | <ref2> | <ref3> | <ref4> }"];
C [label="{ <data> C | <ref1> | <ref2> | <ref3> | <ref4> }"];
D [label="{ <data> D | <ref1> | <ref2> | <ref3> | <ref4> }"];
E [label="{ <data> E | <ref1> | <ref2> | <ref3> | <ref4> }"];
F [label="{ <data> F | <ref1> | <ref2> | <ref3> | <ref4> }"];
{rank=same A}
{rank=same B C D}
{rank=same E F}
A:ref1 -> B
A:ref2 -> C
A:ref3 -> D
C:ref1 -> E
C:ref2 -> F
}
```
使用 C++ 表示節點結構的話：
```cpp!
template<typename T>
struct TreeNode
{
T data;
TreeNode *child1;
TreeNode *child2;
TreeNode *child3;
TreeNode *child4;
};
```
你會注意到，當 tree 的 degree 最大為 $k$ 時，我們就要讓每個節點都準備 $k$ 條 links 的空間
如果有 $n$ 個節點，那就需要 $k\cdot n$ 條 links
但是根據 tree 本身的數學性質我們知道，非空 links 數只會有 $n-1$ 條
因此，這個方法的空間浪費率為 $\frac{nk-(n-1)}{nk}$，大概是 $\frac{k-1}{k}$
如果 $k=1$ 就退化成普通的 linked list 了我們就不討論，所以對 tree 來說 $k=2$ 時浪費率最低，但也達到約 $50\%$
不過這個表示方法很直觀，而且表達 tree 上較有彈性
所以在表達 binary tree (也就是 $k = 2$) 時，我們更習慣用這種方法
## Binary Tree
我們可以簡單記得 binary tree 就是每個節點的 degree $\le 2$ 的 tree
不過要提醒，在資料結構這邊，binary tree 與 tree 還有其他不同的地方，**其實不能說 binary tree 是 tree**
1. binary tree 可以為空 (node 0 個)
2. 有 root 及左右子樹 (這邊強調左右 表示其不同於樹 有左右方向之分)
3. 左右子樹亦為 binary tree
<table>
<tr>
<th>Tree</th>
<th>Binary Tree</th>
</tr>
<tr>
<td>Cannot be empty</td>
<td>Can be empty</td>
</tr>
<tr>
<td>Node degree ≥ 0</td>
<td>0 ≤ Node degree ≤ 2</td>
</tr>
<tr>
<td>Subtrees have no specific order</td>
<td>Subtrees are ordered as left and right</td>
</tr>
</table>
### 性質
假設定 root 所在的 level 為 $1$
1. level $i$ 有 $2^{i-1}$ 個 nodes
2. 高度為 $h$ 的 binary tree 最多有 $2^h-1$ 個 nodes 最少 $h$ 個 nodes
3. 若 $n_d$ 表示 degree 為 $d$ 的 nodes 總數， $n_0 = n_2 + 1$
### 種類
- Skewed Binary Tree
- $n$ 節點高度為 $n$ (root level $=1$)
- Full Binary Tree
- 節點數最大化的 binary tree
- Complete Binary Tree
- 節點增長順序由上而下，同 level 由左而右
- 如果高度為 $h$ 則節點樹介於 $2^{h-1}-1$ 到 $2^h-1$
- 如果 root 的編號為 $1$ 則 $\mathrm{node}_i$ 的若有左右子點，其編號為 $2i, 2i+1$；若有父點，其編號為 $\left[ \frac{i}{2} \right]$
- Strict Binary Tree
- 不存在 degree 為 $1$ 的節點
> [!Caution]
> 要注意的是離散在這邊的定義與資結有點不同
### Binary Tree Traversal
- preorder
- inorder
- postorder
- level order
令 BT 如下：
```graphviz
graph bt{
rankdir=TD;
graph [fontname="DFKai-SB"];
node [fontname="DFKai-SB"];
edge [fontname="DFKai-SB"];
{ rank=same D}
{ rank=same L R }
L [shape=triangle]
R [shape=triangle]
D--L
D--R
}
```
$L$ 跟 $R$ 代表左右子樹，$D$ 代表該樹的 root 則遍歷順序：
<table>
<tr>
<th>Preorder</th>
<th>Inorder</th>
<th>Postorder</th>
</tr>
<tr>
<td>DLR</td>
<td>LDR</td>
<td>LRD</td>
</tr>
</table>
其實很好記：
1. 先走左子樹再走右子樹
2. $D$ 在前就是 preorder ，在中間就是 inorder ，在後面就是 postorder
而 level order 就是 level 從上往下由左向右遍歷
***
例如給你下面的 BT
```graphviz
graph linked_list{
rankdir=TD;
graph [fontname="DFKai-SB"];
node [fontname="DFKai-SB"];
edge [fontname="DFKai-SB"];
{rank=same A}
{rank=same B C}
{rank=same D E F G}
A--B
A--C
B--D
B--E
C--F
C--G
}
```
則遍歷結果：
<table>
<tr>
<th>Preorder</th>
<th>Inorder</th>
<th>Postorder</th>
<th>Level Order</th>
</tr>
<tr>
<td>ABDECFG</td>
<td>DBEAFCG</td>
<td>DEBFGCA</td>
<td>ABCDEFG</td>
</tr>
</table>
***
如果今天反過來給你遍歷順序，那麼怎樣的組合能決定唯一的 BT 呢？
<table>
<tr>
<th style="text-align:center">Inputs</th>
<th style="text-align:center">Can Determine the Unique BT?</th>
</tr>
<tr align="center">
<td>inorder + {preorder, postorder, or level order}</td>
<td>YES</td>
</tr>
<tr align="center">
<td>preorder + postorder</td>
<td>NO</td>
</tr>
<tr align="center">
<td>level order + {preorder or postorder}</td>
<td>NO</td>
</tr>
<tr align="center">
<td>full BT + {preorder, inorder, postorder, level order}</td>
<td>YES</td>
</tr>
<tr align="center">
<td>complete BT + {preorder, inorder, postorder, level order}</td>
<td>YES</td>
</tr>
<tr align="center">
<td>BST + {preorder, postorder, level order}</td>
<td>YES</td>
</tr>
</table>
***
使用 linked list 的方式來表示 tree node 則 BT 的遍歷怎麼寫呢？
下面是節點的結構
```cpp!
template <typename T>
struct TreeNode
{
T data;
TreeNode *left;
TreeNode *right;
TreeNode(const T &val) : data(val), left(nullptr), right(nullptr) {}
};
```
為了表達方便，我們使用 enum class 來表達要選擇哪一種遍歷方式
```cpp!
enum class Traversal
{
PREORDER,
INORDER,
POSTORDER,
LEVELORDER,
};
```
則以 preorder 為例，我們可以很輕易寫出其遞迴演算法：
```cpp!
template <typename Functor>
void preorder(TreeNode<T> *node, Functor func)
{
if (!node)
return;
func(node); // D
preorder(node->left, func); // L
preorder(node->right, func); // R
}
```
> [!Tip]
> `nullptr` 視為 `false` ，所以 `!root` 為 `true` 的情況即 `root == nullptr` (空樹)
記得我們前面講的遍歷記憶法嗎？沒錯，只要記得 DLR 你就能輕鬆寫出 code 了！
同理，inorder 跟 postorder ：
```cpp!
template <typename Functor>
void inorder(TreeNode<T> *node, Functor func)
{
if (!node)
return;
inorder(node->left, func); // L
func(node); // D
inorder(node->right, func); // R
}
template <typename Functor>
void postorder(TreeNode<T> *node, Functor func)
{
if (!node)
return;
postorder(node->left, func); // L
postorder(node->right, func); // R
func(node); // D
}
```
至於 level order 用 BFS：
```cpp!
template <typename Functor>
void levelorder(TreeNode<T> *node, Functor func)
{
if (!node)
return;
std::queue<TreeNode<T> *> q;
q.push(node);
while (!q.empty())
{
TreeNode<T> *curr = q.front();
q.pop();
func(curr);
if (curr->left)
q.push(curr->left);
if (curr->right)
q.push(curr->right);
}
}
```
如此，我們便能簡單寫出一個列印 BT 的 method：
```cpp!
void printBT(const Traversal &policy)
{
auto printFunc = [](TreeNode<T> *node)
{
std::cout << node->data << " ";
};
switch (policy)
{
case Traversal::PREORDER:
preorder(root, printFunc);
break;
case Traversal::INORDER:
inorder(root, printFunc);
break;
case Traversal::POSTORDER:
postorder(root, printFunc);
break;
case Traversal::LEVELORDER:
levelorder(root, printFunc);
break;
default:
std::cerr << "Invalid traversal policy!\n";
break;
}
std::cout << "\n";
}
```
測試一下
```graphviz
graph linked_list{
rankdir=TD;
graph [fontname="DFKai-SB"];
node [fontname="DFKai-SB"];
edge [fontname="DFKai-SB"];
{rank=same A}
{rank=same B D}
{rank=same NULL C E F}
A--B
A--D
B--NULL
B--C
D--E
D--F
NULL [fontsize="0pt"]
}
```
```cpp!
int main()
{
BinaryTree<char> bt;
bt.root = new TreeNode('A');
TreeNode<char> *node1 = new TreeNode('B');
TreeNode<char> *node2 = new TreeNode('C');
TreeNode<char> *node3 = new TreeNode('D');
TreeNode<char> *node4 = new TreeNode('E');
TreeNode<char> *node5 = new TreeNode('F');
// Build the BT
bt.root->left = node1;
bt.root->right = node3;
node1->right = node2;
node3->left = node4;
node3->right = node5;
std::cout << "Preorder Traversal:\n";
bt.printBT(Traversal::PREORDER);
std::cout << "\nInorder Traversal:\n";
bt.printBT(Traversal::INORDER);
std::cout << "\nPostorder Traversal:\n";
bt.printBT(Traversal::POSTORDER);
std::cout << "\nLevel-order Traversal:\n";
bt.printBT(Traversal::LEVELORDER);
return 0;
}
```
***
一些 BT 有可能會考的應用題
#### 判斷兩樹相等
```cpp!
friend bool operator==(const BinaryTree<T> &lhs, const BinaryTree<T> &rhs)
{
std::function<bool(TreeNode<T> *, TreeNode<T> *)> btEqual = [&](TreeNode<T> *a, TreeNode<T> *b)
{
if (!a && !b)
return true;
if (!a || !b)
return false;
return (a->data == b->data) && btEqual(a->left, b->left) && btEqual(a->right, b->right);
};
return btEqual(lhs.root, rhs.root);
}
friend bool operator!=(const BinaryTree<T> &lhs, const BinaryTree<T> &rhs) { return !(lhs == rhs); }
```
#### 複製 BT
```cpp!
TreeNode<T> *btCopy(TreeNode<T> *node)
{
if (!node)
return nullptr;
TreeNode<T> *newNode = new TreeNode<T>(node->data);
newNode->left = btCopy(node->left);
newNode->right = btCopy(node->right);
return newNode;
}
```
現在我們可以進一步補充我們的 constructor 跟 `=` operator
```cpp!
/**
* @brief Default constructor (empty tree)
*/
BinaryTree() noexcept : root{nullptr} {}
/**
* @brief Copy constructor
*/
BinaryTree(const BinaryTree<T> &other) noexcept : root(btCopy(other.root)) {}
/**
* @brief Move constructor
*/
BinaryTree(BinaryTree<T> &&other) noexcept : root(other.root) { other.root = nullptr; }
```
```cpp!
/**
* @brief Copy assigment operator
*/
BinaryTree<T> &operator=(const BinaryTree<T> &other)
{
if (this != &other)
{
btDestroy();
root = btCopy(other.root);
}
return *this;
}
/**
* @brief Move assignment operator
*/
BinaryTree<T> &operator=(BinaryTree<T> &&other) noexcept
{
if (this != &other)
{
root = other.root;
other.root = nullptr;
}
return *this;
}
```
#### Expression BT
可以想像是 compiler 建立 parsing tree or syntax tree 的作法
原則：
1. leaf 表示 operand
2. non-leaf 表示 operator
3. 優先權大的鄰近 operator level 較大 (較下面)
例如給 `a + b * c - d / e`
把這想成是 BT inorder 的結果
則 postorder 為 `abc * + de / -`
只要有這兩個遍歷結果就能建構回樹了
```graphviz
graph linked_list{
rankdir=TD;
graph [fontname="DFKai-SB"];
node [fontname="DFKai-SB"];
edge [fontname="DFKai-SB"];
{rank=same A}
{rank=same B C}
{rank=same D E F G}
{rank=same H I}
A--B
A--C
B--D
B--E
C--F
C--G
E--H
E--I
A [label="-"]
B [label="+"]
C [label="/"]
D [label="a"]
E [label="*"]
F [label="d"]
G [label="e"]
H [label="b"]
I [label="c"]
}
```
我覺得這邊只要會手寫作答的部份就好了
#### 其他
這邊附上截止至本文撰寫時，本人印象中有解過，LeetCode 上跟 BT 有關的題目
- [2415. Reverse Odd Levels of Binary Tree](https://hackmd.io/@RyoukiWei/leetcode2415)
- [2458. Height of Binary Tree After Subtree Removal Queries](https://hackmd.io/@RyoukiWei/leetcode2458)
- [951. Flip Equivalent Binary Trees](https://hackmd.io/@RyoukiWei/leetcode951)
- [2641. Cousins in Binary Tree II](https://hackmd.io/@RyoukiWei/leetcode2641)
- [2583. Kth Largest Sum in a Binary Tree](https://hackmd.io/@RyoukiWei/leetcode2583)
- [979. Distribute Coins in Binary Tree](https://hackmd.io/@RyoukiWei/leetcode979)
- [2331. Evaluate Boolean Binary Tree](https://hackmd.io/@RyoukiWei/leetcode2331)
- [226. Invert Binary Tree](https://hackmd.io/@RyoukiWei/leecode226)
- [257. Binary Tree Paths](https://hackmd.io/@RyoukiWei/leetcode257)
- [823. Binary Trees With Factors](https://hackmd.io/@RyoukiWei/leetcode823)
- [543. Diameter of Binary Tree](https://hackmd.io/@RyoukiWei/leetcode543)
## Binary Search Tree
是 BT ，故可以為空
若不為空：
- root 之左子樹上任意節點之值小於 root 之值
- root 之右子樹上任意節點之值大於 root 之值
- root 之左右子樹亦為 BST
> [!Tip]
> BST 的 inorder traversal 必定是由小到大排列輸出
```cpp!
namespace riklib
{
template <typename T>
struct Iterator
{
using Node = TreeNode<T>;
Node *curr;
std::vector<Node *> ancestors;
Iterator(Node *root = nullptr)
{
curr = root;
// find smallest element in BST
while (curr && curr->left)
{
ancestors.push_back(curr);
curr = curr->left;
}
}
T &operator*() const { return curr->data; }
friend bool operator==(const Iterator &lhs, const Iterator &rhs) { return lhs.curr == rhs.curr; }
friend bool operator!=(const Iterator &lhs, const Iterator &rhs) { return !(lhs == rhs); };
};
template <typename T>
class BinarySearchTree : public BinaryTree<T>
{
public:
using Node = TreeNode<T>;
using iterator = Iterator<T>;
BinarySearchTree() {}
iterator begin() noexcept { return iterator(this->root); }
iterator begin() const noexcept { return iterator(this->root); }
iterator cbegin() const noexcept { return iterator(this->root); }
iterator end() noexcept { return iterator(nullptr); }
iterator end() const noexcept { return iterator(nullptr); }
iterator cend() const noexcept { return iterator(nullptr); }
};
} // namespace riklib
```
### Inorder predecessor and successor
我們知道 BST 的 inorder 就是 sorted order
故 inorder successor 即 sorted order 中的下一位； inorder predecessor 同理為上一位
對應我們 `Iterator` 實作便是 `++` 跟 `--` 運算
這邊我大致提供一個簡單的實作以供參考
我們給 `TreeNode` 增加 `parent` 指標
`Iterator` 更新後如下：
```cpp!
template <typename T>
struct Iterator
{
using Node = TreeNode<T>;
Node *curr;
Iterator(Node *root = nullptr)
{
curr = root;
// find smallest element in BST
while (curr && curr->left)
curr = curr->left;
}
T &operator*() const { return curr->data; }
friend bool operator==(const Iterator &lhs, const Iterator &rhs) { return lhs.curr == rhs.curr; }
friend bool operator!=(const Iterator &lhs, const Iterator &rhs) { return !(lhs == rhs); };
Iterator &operator++()
{
if (!curr)
throw std::out_of_range("Iterator out of range");
if (curr->right)
{
curr = curr->right;
while (curr->left)
curr = curr->left;
}
else
{
Node *parent = curr->parent;
while (parent && parent->right == curr)
{
curr = parent;
parent = parent->parent;
}
curr = parent;
}
return *this;
}
Iterator operator++(int)
{
Iterator temp = *this;
++(*this);
return temp;
}
Iterator &operator--()
{
if (!curr)
throw std::out_of_range("Iterator out of range");
if (curr->left)
{
curr = curr->left;
while (curr->right)
curr = curr->right;
}
else
{
Node *parent = curr->parent;
while (parent && parent->left == curr)
{
curr = parent;
parent = parent->parent;
}
curr = parent;
}
return *this;
}
Iterator operator--(int)
{
Iterator temp = *this;
--(*this);
return temp;
}
Iterator operator+(int n) const
{
Iterator it = *this;
for (int i = 0; i < n; ++i)
{
++it;
}
return it;
}
Iterator operator-(int n) const
{
Iterator it = *this;
for (int i = 0; i < n; ++i)
{
--it;
}
return it;
}
Iterator &operator+=(int n)
{
for (int i = 0; i < n; ++i)
++(*this);
return *this;
}
Iterator &operator-=(int n)
{
for (int i = 0; i < n; ++i)
--(*this);
return *this;
}
};
```
### Insert
我們就依照 BST 的規則找正確的位置放置新節點即可
多次 `insert()` 便可建立 BST
BST 建立之結構受 input 順序影響，如果給 sorted input 則會得 skewed BST
範例：
`input: 5, 8, 9, 3, 1, 4, 6, 2, 7`
```cpp!
/**
* @brief Insert a value into the BST.
*
* @param value The value to insert.
* @return A pair containing an iterator to the inserted node (or the node
* with the same value) and a boolean indicating success.
*/
std::pair<iterator, bool> insert(const T &val)
{
Node **curr = &this->root;
Node *parent = nullptr;
while (*curr)
{
parent = *curr;
if (val == (*curr)->data)
// Value already exists in the BST
return {iterator(*curr), false};
if (val < (*curr)->data)
curr = &(*curr)->left;
else
curr = &(*curr)->right;
}
*curr = new Node(val);
(*curr)->parent = parent;
return {iterator(*curr), true};
}
```
### Delete
1. 找到目標 `x`
2. 分三種情況：
1. `x` is leaf: 直接砍掉
2. `deg(x) == 1` 把 `x` 的 parent 指向 `x` 的 child 再砍掉 `x`
3. `deg(x) == 2` 找左子樹最大值 or 右子樹最小值 令為 `y` 以 `y` 取代 `x` 再 `delete(y)` (原本位置的 `y`)
例如原本的 BST
砍 5 ，假設採用左子樹最大值則過程：
```cpp!
/**
* @brief Erases the node at the given position in the BST.
*
* @param pos Iterator pointing to the node to erase. Must be a valid iterator
* obtained from this tree or its end iterator.
* @return Iterator pointing to the next in-order node after the erased node.
* If the erased node was the last in-order node, returns end().
*/
iterator erase(iterator pos)
{
if (!pos.curr)
return end(); // Return end iterator if the position is invalid
Node **parent_link = &this->root;
Node *target = this->root;
while (target && target != pos.curr)
{
if (pos.curr->data < target->data)
parent_link = &target->left, target = target->left;
else
parent_link = &target->right, target = target->right;
}
if (!target)
return end();
// Case 1: Node is a leaf node
if (!target->left && !target->right)
{
delete target;
*parent_link = nullptr;
}
// Case 2: Node has only one child
else if (!target->left || !target->right)
{
Node *child = target->left ? target->left : target->right;
delete target;
*parent_link = child;
if (child)
child->parent = *parent_link;
}
// Case 3: Node has two child
else
{
// Find the inorder successor (smallest node in the right subtree)
Node **successor_link = &target->right;
Node *successor = target->right;
while (successor->left)
successor_link = &successor->left, successor = successor->left;
// Replace target's value with successor's value
target->data = successor->data;
// Case 1 or 2 for the successor (successor->left must be nullptr now)
*successor_link = successor->right;
if (successor->right)
successor->right->parent = successor->parent;
delete successor;
}
if (!this->root)
return end();
Node *next = nullptr;
if (target->right)
{
next = target->right;
while (next->left)
next = next->left;
}
else
{
Node *parent = target->parent;
while (parent && parent->right == target)
{
target = parent;
parent = parent->parent;
}
next = parent;
}
if (next == target)
return begin();
return iterator(next);
}
```
因為普通 BST 的 `insert()` 相對簡單，所以對 iterator 的影響很好處理
但是 `erase()` 就不一樣了，我們要注意該操作對 iterator 有效性的破壞
下面是我大致 debug 用的 code：
```cpp!
#include "binary_search_tree.hpp"
using namespace riklib;
int main()
{
BinarySearchTree<int> bst;
bst.insert(4);
bst.insert(1);
bst.insert(0);
bst.insert(3);
bst.insert(2);
bst.printBT(Traversal::PREORDER);
for (auto it = bst.begin(); it != bst.end();)
{
it = bst.erase(it);
}
std::cout << (bst.root == nullptr) << "\n";
bst.printBT(Traversal::PREORDER);
return 0;
}
```
因為每次 `erase()` 會破壞 iterator 之有效性，所以我們要將 `it` 更新成 `erase()` 回傳的下個位置
有成功砍完整棵 BST ，最後 `bst` 變回了空樹
### Search
```cpp!
/**
* @brief Finds a node containing the given value in the BST.
*
* @param val The value to search for in the tree.
* @return Iterator pointing to the node containing the value if found, or the end
* iterator if the value is not found.
*/
iterator find(const T &val)
{
Node *curr = this->root;
while (curr)
{
if (val == curr->data)
return iterator(curr);
curr = val < curr->data ? curr->left : curr->right;
}
return end();
}
```
看到這邊，相信各位算是基礎認識 BST 了
那各位會發現，best case 跟 average case 下 `find()` 的時間複雜度是 $O(\lg n)$ 沒有什麼問題
但如果 BST 是 skewed tree 的話，就會有 worst case $O(n)$
`insert()` 跟 `erase()` 也跟 `find()` 一樣
這問題就是 BST 的高度並未受到控制，而都叫 binary **search** tree 了，`find()` 的時間複雜度我們肯定是希望能好點，不要退化到線性時間
在未來，我們將會討論高度平衡的 BST 來解決這問題
### Find k-th smallest in BST
最直覺的方法當然是按照 inorder 等第 `k` 個出現
但我們有其他作法
關鍵是我們在多紀錄每個節點其左子樹的節點個數
如此一來我們便可以輕鬆找出第 `k` 小了
大致 pseudocode 長這樣：
```pseudocode!
FindKthSmallest(node, k)
// node: the root of the current subtree
// k: the rank of the smallest element to find
let r ← node.left.size + 1 // Compute the rank of node within its subtree
if k = r then
return node // node is the k-th smallest element
else if k < r then
return FindKthSmallest(node.left, k) // Recur into the left subtree
else
return FindKthSmallest(node.right, k - r) // Recur into the right subtree with adjusted rank
```
`k == r` 的 case 不必多說
`k < r ` 時，表示要找的目標在當前根節點的左子樹裡；`k > r` 時，表示左子樹裡沒有想要的，前 `r` 個後面都不用看了，前 `k` 個少了 `r` 個，所以所求是剩下元素中前 `k - r` 小的那個
這個可以記一下大概演算法怎麼寫
不難，但經典
## Heap
- 為 complete BT
- 以 Max-Heap 來說父點必大於其左右子點；Min-Heap 則小於
- Root Max-Heap 為最大值 而 Min-Heap 為最小值
前面講過 complete BT 會發現這種 BT 其實節點長很滿
這種時候其實反而使用 array 保存更適合
Heap 可以用來製作 priority queue 也能用來 heap sort
| Operations | Time Complexity |
| :-------: | :--------: |
| **Insert** | $O(\lg n)$ |
| **Delete-Max** (**Delete-Min**)| $O(\lg n)$ |
| **Heapifty** | $O(\lg n)$ |
| **Find-Max** (**Find-Min**)| $O(1)$ |
| **Build** | $O(n)$ |
| **Decrease key** | $O(\lg n)$ |
| **Merge** | $O(n)$ |
***
以下提供基礎的 binary heap 實作
```cpp!
namespace riklib
{
// Defualt: Min-Heap
template <typename T, typename Compare = std::less<T>>
class BinaryHeap
{
private:
std::vector<T> heap;
Compare compare;
public:
using iterator = typename std::vector<T>::iterator;
using const_iterator = typename std::vector<T>::const_iterator;
BinaryHeap() noexcept = default;
explicit BinaryHeap(const Compare &comp) : compare(comp) {}
BinaryHeap(std::initializer_list<T> init, const Compare &comp = Compare()) : heap(init), compare(comp) { buildHeap(); }
BinaryHeap(const BinaryHeap &other) = default;
BinaryHeap(BinaryHeap &&other) noexcept = default;
BinaryHeap &operator=(const BinaryHeap &other) = default;
BinaryHeap &operator=(BinaryHeap &&other) noexcept = default;
~BinaryHeap() = default;
iterator begin() noexcept { return heap.begin(); }
const_iterator begin() const noexcept { return heap.begin(); }
const_iterator cbegin() const noexcept { return heap.cbegin(); }
iterator end() noexcept { return heap.end(); }
const_iterator end() const noexcept { return heap.end(); }
const_iterator cend() const noexcept { return heap.cend(); }
/**
* @brief Inserts a value into the heap while maintaining the heap property.
* @param val The value to insert.
*/
void push(const T &val)
{
heap.push_back(val);
size_t idx = heap.size() - 1;
while (idx > 0)
{
size_t parent = (idx - 1) / 2;
if (compare(heap[idx], heap[parent]))
{
std::swap(heap[idx], heap[parent]);
idx = parent;
}
else
break;
}
}
/**
* @brief Removes the top element from the heap.
* @throw std::runtime_error if the heap is empty.
*/
void pop()
{
if (heap.empty())
throw std::runtime_error("Cannot pop from an empty heap.");
std::swap(heap.front(), heap.back());
heap.pop_back();
if (!heap.empty())
heapify(0);
}
/**
* @brief Returns the top element of the heap.
* @throws std::runtime_error if the heap is empty.
* @return const T& The top element of the heap.
*/
const T &top() const
{
if (heap.empty())
throw std::runtime_error("Heap is empty.");
return heap.front();
}
/**
* @brief Checks if the heap is empty.
* @return true if the heap is empty, false otherwise.
*/
bool empty() const noexcept { return heap.empty(); }
/**
* @brief Returns the number of elements in the heap.
* @return size_t The size of the heap.
*/
size_t size() const noexcept { return heap.size(); }
private:
void heapify(size_t idx)
{
const size_t n = heap.size();
size_t target = idx;
size_t left = 2 * idx + 1;
size_t right = 2 * idx + 2;
if (left < n && compare(heap[left], heap[target]))
target = left;
if (right < n && compare(heap[right], heap[target]))
target = right;
if (target != idx)
{
std::swap(heap[idx], heap[target]);
heapify(target);
}
}
void buildHeap()
{
const size_t n = heap.size();
for (size_t i = n / 2; i > 0; --i)
{
heapify(i - 1);
}
}
};
}
```
### build
我們有兩種方式來初始建構 heap：
1. top-down
2. bottom-up
top-down 很簡單，就是依照輸入順序一個個 `push()`(insert) 進去
可是這樣的時間複雜度其實是 $O(n\lg n)$
$$
\sum\limits_{i=1}^{n}\lg i = \lg (n!) = O(n\lg n)
$$
另一種方式即 bottom-up
我們是先讓所有元素都放進 array (可以想成先填進 complete BT 中)
接著使用 `heapify` 的方式調整陣列使其符合 heap 的性質
這樣講有點抽象 具體來說就是從最後一個 parent 開始往上使每棵子樹皆符合 heap 性質直到 root
這樣的時間複雜度就是 $O(n)$ 了
### merge
```cpp!
/**
* @brief Merges another binary heap into this heap.
* The merge operation maintains the heap property.
* @param other The other binary heap to merge with this heap.
*/
void merge(const BinaryHeap &other) noexcept
{
heap.insert(heap.end(), other.heap.begin(), other.heap.end());
buildHeap();
}
```
## 【資工考研】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)
Sign in with Wallet
Connect another wallet