# 【資工考研】DS: Binary Tree (2) Threaded Binary Tree + Double-ended Priority Queue
## Threaded Binary Tree
我們[前面](https://hackmd.io/@RyoukiWei/binary_tree_1#Binary-Tree)談過使用 linked list 表示 binary tree 會造成的空間浪費
那麼我們能否更充分地利用它們呢？
Threaded 有以下規則：
1. `if x->left == nullptr` 指向其 predecessor
2. `if x->right == nullptr` 指向其 successor
> A binary tree is threaded by making all right child pointers that would normally be null point to the in-order successor of the node (if it exists), and all left child pointers that would normally be null point to the in-order predecessor of the node.
如下圖：
<center><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/7/7a/Threaded_tree.svg/220px-Threaded_tree.svg.png" alt="Threaded Binary Tree from Wiki"></center>
[source](https://en.wikipedia.org/wiki/Threaded_binary_tree)
***
除了本來就會有的 root 外，我們還需要再一個 dummy node 其 `right` 指向自己，`left` 指向 root
並且我們需要標記其左右兩指標的作用是否為引線 (`true` 表示是)
以下為空樹的 dummy node
我們在節點左右兩邊新增布林值用來區分該條 link 是否為引線
因為 dummy node 的 `right` 指向自己，所以不是引線 (`false`)
```graphviz
digraph structure {
rankdir=LR;
graph [fontname="DFKai-SB"];
node [fontname="DFKai-SB" shape=record, width=1.2, height=0.6];
edge [fontname="DFKai-SB"];
A [label="{ <lt> false | <left> left | <data> data | <right> right | <rt> true }"];
A:left:s -> A:lt [style=dashed];
A:right:s -> A:rt:r;
}
```
Threaded BT 的節點結構如下
```cpp!
template <typename T>
struct ThreadedTreeNode
{
T data;
ThreadedTreeNode *left;
ThreadedTreeNode *right;
bool lthread;
bool rthread;
ThreadedTreeNode(const T &val) : data(val), left(nullptr), right(nullptr), lthread(true), rthread(true) {}
};
```
我們需要在 constructor 設置好 dummy：
```cpp!
using Node = ThreadedTreeNode<T>;
ThreadedBinaryTree() : root(nullptr), dummy(new Node(T()))
{
dummy->left = dummy;
dummy->right = dummy;
dummy->rthread = false;
}
```
在 Threaded BT 的篇章我們至少要知道以下三種操作：
1. `inSuc()` and `inPre()` ，也就是中序後繼者與中序先行者
2. 簡化過後的中序遍歷
3. 指定位置插入
演算法都不難
### `inSuc(x)` and `inPre(x)`
以找後繼者為例：
1. 如果 `x->rthread == true` 表示 `x` 沒有實際上的右子點，根據定義，其右引線會指向後繼者，故 `x->right` 即為所求
2. 反之，就像 BT 一樣，找右子樹最左的點即為所求
```cpp!
/**
* @brief Find the inorder successor of the given node in threaded BT.
* @param node Pointer to the current node.
* @return Pointer to the inorder successor of the node.
*/
Node *inSuc(Node *node)
{
if (node->rthread)
return node->right;
node = node->right;
while (!node->lthread)
node = node->left;
return node;
}
```
除了檢查左邊是否為引線，根據定義， `x` 的後繼者的先行者就是 `x`，這樣看也是可以的
> [!Note]
> 試問：那 `inSuc(dummy)` 會得到什麼？
>
> 很簡單，`dummy->right` 指向它自己，`dummy->rthread == false`
> 故我們便會從 `dummy->right` 也就是它自己開始，一直往左走，先到 root 最後走到的即整棵樹最左的那個 leaf (中序順序最開頭)
### Inorder Traversal
現在我們找後繼者可簡單了，那 inorder traversal 只要從 dummy 開始不斷找後繼者，直到重回 dummy 即可
```cpp!
/**
* @brief Preforn an inorder traversal of the threaded BT.
* @tparam Functor A callable type to apply to each node.
* @param func A function or callable object to process node.
*/
template <typename Functor>
void inorderTraversal(Functor func)
{
Node *curr = inSuc(dummy);
while (curr != dummy)
{
func(curr);
curr = inSuc(curr);
}
}
```
### Insert `y` as a child of `x`
以插入右子點為例：
1. 如果 `x` 原先沒有右子點，把 `x->right` 指向 `y` ，`y` 的先行者即 `x` ，後繼者則為原先 `x` 的後繼者
2. 如果 `x` 本來是有右子點的，把 `x->right` 指向 `y` ，`y->right` 指向原本的 `x->right`，`y` 的先行者即 `x`，原本的 `x->right` 的先行者變成了 `y`
這邊強調先行者、後繼者代表在處理引線
```cpp!
/**
* @brief Insert the target node as a child if tge given node.
* @param node Pointer to the parent node where the target will be inserted.
* @param target Pointer to the node to be inserted.
* @param asRightChild Boolean flag indicating insertion as the right child (default: true).
* @return True if the insertion was seccessful, false otherwise.
*/
bool insertAt(Node *node, Node *target, bool asRightChild = true)
{
if (!root)
setRoot(node);
if (!node || !target)
return false;
if (asRightChild)
{
target->rthread = node->rthread;
target->right = node->right;
target->lthread = true;
target->left = node;
node->rthread = false;
node->right = target;
if (!target->rthread)
inSuc(target)->left = target;
}
else
{
target->lthread = node->lthread;
target->left = node->left;
target->rthread = true;
target->right = node;
node->lthread = false;
node->left = target;
if (!target->lthread)
inPre(target)->right = target;
}
return true;
}
```
## Double-ended Priority Queue
我們說過[Heap](https://hackmd.io/@RyoukiWei/binary_tree_1#Heap)能夠用來作為 priority queue，不過我們只能從挑最小值跟最大值兩個操作中挑一種，也就是要每次挑最小值就用 Min-Heap 但不適合對此挑最大值；想挑最大值就用 Max-Heap 但同理就不適合挑最小值
Double-ended priority queue 則設計成類似 priority queue 的資料結構，但能同時支援有效地刪除最小值跟最大值
以下幾種資料結構適合用來製作 double-ended priority queue
- Min-Max Heap
- Deap
- SMMH
| Operations | Time Complexity |
| :-------: | :--------: |
| **Insert** | $O(\lg n)$ |
| **Delete-Max** (**Delete-Min**)| $O(\lg n)$ |
| **Find-Max** (**Find-Min**)| $O(1)$ |
### Min-Max Heap
Min-Max heap 也是 complete binary tree
不過跟 binary heap 的差別是它每層是 min max 交錯
什麼意思呢？
Min-Max heap 的 root 所在是 min level，root 是整棵樹中值最小者
對於 min-level 的節點，其必定是以該節點作為 root 的子樹中值最小者；對於 max-level 的節點，其必定為以該節點作為 root 的子樹中值最大者
> [!Tip]
> Max-Min heap 就反過來，root 是最大值
因為 Min-Max heap 也是 complete binary tree ，所以同樣適合用 array 來表示
***
```cpp!
template <typename T>
class MinMaxHeap
{
public:
MinMaxHeap() : m_h() {}
/**
* @brief Inserts a new element into the Min-Max heap.
* @param val The value to be inserted
*/
void push(const T &val)
{
m_h.push_back(val);
bubbleUp(m_h.size() - 1);
}
/**
* @brief Removes the smallest element (root) from the Min-Max heap.
* @throws std::underflow_error if the heap is empty.
*/
void popMin()
{
if (m_h.empty())
throw std::underflow_error("Min-Max is empty.");
std::swap(m_h.front(), m_h.back());
m_h.pop_back();
if (!m_h.empty())
trickleDown(0);
}
/**
* @brief Removes the largest element from the Min-Max heap.
* @throws std::underflow_error if the heap is empty.
*/
void popMax()
{
if (m_h.empty())
throw std::underflow_error("Min-Max is empty.");
size_t maxIdx;
if (m_h.size() < 3)
maxIdx = m_h.size() - 1;
else
maxIdx = (m_h[1] > m_h[2]) ? 1 : 2;
std::swap(m_h[maxIdx], m_h.back());
m_h.pop_back();
if (maxIdx < m_h.size())
trickleDown(maxIdx);
}
/**
* @brief Retrieces the smallest element (root) from the Min-Max heap.
* @return A reference to the smallest element.
* @throws std::underflow_error if the heap is empty.
*/
T &min() const
{
if (m_h.empty())
throw std::underflow_error("Min-Max is empty.");
return m_h.front();
}
/**
* @brief Retrieces the largest element from the Min-Max heap.
* @return A reference to the largest element.
* @throws std::underflow_error if the heap is empty.
*/
T &max() const
{
if (m_h.empty())
throw std::underflow_error("Min-Max is empty.");
if (m_h.size() == 1)
return m_h.front();
if (m_h.size() == 2)
return m_h[1];
return std::max(m_h[1], m_h[2]);
}
/**
* @brief Returns the number of elements in the heap.
* @return The size of the heap.
*/
size_t size() const noexcept { return m_h.size(); }
/**
* @brief Removes all elements from the heap.
*/
void clear() { m_h.clear(); }
private:
std::vector<T> m_h;
size_t getParentIdx(size_t idx) const
{
assert(idx > 0);
return (idx - 1) / 2;
}
size_t getLeftChildIdx(size_t idx) const { return 2 * i + 1; }
size_t getRightChildIdx(size_t idx) const { return 2 * i + 2; }
bool isMinLevel(size_t idx) const { return static_cast<int>(log2(i + 1)) & 1; }
/**
* @brief Helper function for `push()`.
*/
void bubbleUp(size_t idx)
{
if (idx == 0)
return;
size_t parent = getParentIdx(idx);
if (isMinLevel(idx))
{
if (m_h[idx] > m_h[parent])
{
std::swap(m_h[idx], m_h[parent]);
bubbleUpMax(parent);
}
else
bubbleUpMin(idx);
}
else
{
if (m_h[idx] < m_h[parent])
{
std::swap(m_h[idx], m_h[parent]);
bubbleUpMin(parent);
}
else
bubbleUpMax(idx);
}
}
void bubbleUpMin(size_t idx)
{
size_t grandparent = getParentIdx(getParentIdx(idx));
if (idx > 2 && m_h[idx] < m_h[grandparent])
{
std::swap(m_h[idx], m_h[grandparent]);
bubbleUpMin(grandparent);
}
}
void bubbleUpMax(size_t idx)
{
size_t grandparent = getParentIdx(getParentIdx(idx));
if (idx > 2 && m_h[idx] > m_h[grandparent])
{
std::swap(m_h[idx], m_h[grandparent]);
bubbleUpMax(grandparent);
}
}
void trickleDown(size_t idx)
{
if (isMinLevel(idx))
trickleDownMin(idx);
else
trickleDownMax(idx);
}
void trickleDownMin(size_t idx)
{
size_t j = getChildOrGrandchild(idx, true);
if (j >= m_h.size())
return;
if (m_h[j] < m_h[idx])
{
std::swap(m_h[j], m_h[idx]);
if (j >= getLeftChildIdx(getLeftChildIdx(idx)))
{
size_t parent = getParentIdx(j);
if (parent < m_h.size() && m_h[j] > m_h[parent])
std::swap(m_h[j], m_h[parent]);
trickleDownMin(j);
}
}
}
void trickleDownMax(size_t idx)
{
size_t j = getChildOrGrandchild(idx, false);
if (j >= m_h.size())
return;
if (m_h[j] > m_h[idx])
{
std::swap(m_h[j], m_h[idx]);
if (j >= getLeftChildIdx(getLeftChildIdx(idx)))
{
size_t parent = getParentIdx(j);
if (parent < m_h.size() && m_h[j] < m_h[parent])
std::swap(m_h[j], m_h[parent]);
trickleDownMax(j);
}
}
}
size_t getChildOrGrandchild(size_t idx, bool findMin) const
{
const size_t n = m_h.size();
size_t res = idx;
for (size_t child = getLeftChildIdx(idx); child <= getRightChildIdx(idx) && child < n; ++child)
{
if ((findMin && m_h[child] < m_h[res]) || (!findMin && m_h[child] > m_h[res]))
res = child;
for (size_t grandchild = getLeftChildIdx(child); grandchild <= getRightChildIdx(child) && grandchild < n; ++grandchild)
{
if ((findMin && m_h[grandchild] < m_h[res]) || (!findMin && m_h[grandchild] > m_h[res]))
res = grandchild;
}
}
return res;
}
};
```
### Deap
- root 不存資料
- root 的左子樹為 Min-Heap
- root 的右子樹為 Max-Heap
- 如果 $i$ 在 root 的左子樹，$j = 2^{\left\lfloor \lg i \right\rfloor - 1}$ 為其在 root 右子樹對應的點 (如果 $j$ 不存在，則 $j = \frac{j}{2} = 2^{\left\lfloor \lg i \right\rfloor - 2}$) ，$i$ 節點的值不可超過 $j$ 的值
插入的部份，會 binary heap 的插入就差不多了，剩下就是讓 $i$ 跟其對應點 $j$ 符合規則
刪除的部份，以刪最小為例，一樣就是先把 Min-Heap 那的最小一路跟其最小子點 swap 直到 leaf ，然後我們把整棵 Min-Max heap 最後一個點拔下來做插入
最容易忘記的大概就是要比較 $i$ 跟 $j$ 它們的值，要記得檢查
### SMMH
也是 complete binary tree，root 不存資料
要符合以下規則：
1. left sibling $\le$ right sibling data
2. 若某節點具祖父節點，則其祖父節點的左子點必定 $\le$ 該節點
3. 若某節點具祖父節點，則其祖父節點的右子點必定 $\ge$ 該節點
總結一下上面的規則，可以得出：
**任一子樹的最小值即其 root 的左子點、最大值即其 root 的右子點**
這是一個很方便手寫時檢查有沒有做對的性質
插入的方法，先放在整棵樹最後面 (新增在陣列最後面)，重複檢查：
- 1.是否滿足？如果不滿足，左右兄弟 swap
- 2.跟 3.是否皆滿足？如果不滿足，往上 (or 斜上)調整
刪除的方法應該也猜出來了，先把目標跟陣列最後的元素 swap 並 pop back (這樣目標就山掉了)，接著一樣檢查並調整直到規則都滿足了 (以 `popMin()` 來說， 3.不必檢查，因為該性質不會被影響到)
我只講怎麼操作的話，代表我覺得了解手寫怎麼寫就好，沒想過怎麼寫 code 不成大礙
## 【資工考研】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