---
hackpadID: LT70ksJxfIU
hackpadWorkspace: tossug
tags: hackpad-import, tossug
---
# DS 讀書會 - 第 12 週

02/10/2015

[« 回首頁](/JwdmDZwMwE3BacBGApgDngFkwYx/NAVjQxlgCZgkdo0AjNIA)

## 討論範圍

* Trees and Tree Algorithms (1/2)
* Objectives - Programming Exercises

## 預定進度

* Trees and Tree Algorithms (2/2)
* Objectives - Programming Exercises

## 認領狀態

* Search Tree Implementation
* → 待認領 ←
* AVL Tree Implementation
* → 待認領 ←

## 心得筆記

**List of Lists Representation**

* root = ’a’
* left_subtree = [b, [d, [], []], [e, [], []]]
* right_subtree = [c, [f, [], []], []]
* myTree = [root, left_subtree, right_subtree]

root: myTree[0]

left_subtree: myTree[1]

right_subtree: myTree[2]

**Nodes and References**


A Simple Tree Using a Nodes and References Approach

--

**Binary Heap**

Binary heap只是找min/max node、insert a node，沒有排序

找min/max時是O(1)，變更(insert/delete)時是O(n log n)。取min/max時快，把時間花在變更。

有分 min heap 和 max heap，通常用來做 priority queue。


full binary tree, complete binary tree, perfect binary tree

由於 complete binary tree 的特性，根據某節點的位置 p，很容易算出節點的位置。

左邊子節點是 2p，右邊子節點是 2p + 1，父節點是 p // 2。

Binary heap 不能做為排序完的結果，而且只能從 root 取值。

Binary tree 有可能退化為一直線，因此需要做平衡。

Linux kernel scheduler

[](https://www.kernel.org/doc/Documentation/scheduler/)[https://www.kernel.org/doc/Documentation/scheduler/](https://www.kernel.org/doc/Documentation/scheduler/)

更多 scheduler 相關內容請參照 [Linux 讀書會第 13 週筆記](/gnQyhcXcjtT)。

Linux kernel 紅黑樹

[](http://www.kerneltravel.net/jiaoliu/kern-rbtree.html)[http://www.kerneltravel.net/jiaoliu/kern-rbtree.html](http://www.kerneltravel.net/jiaoliu/kern-rbtree.html)

紅黑樹 deletion

[](https://www.ptt.cc/bbs/b98902HW/M.1294926798.A.8DD.html)[https://www.ptt.cc/bbs/b98902HW/M.1294926798.A.8DD.html](https://www.ptt.cc/bbs/b98902HW/M.1294926798.A.8DD.html)

[2-3-4 tree](http://en.wikipedia.org/wiki/2–3–4_tree) 可用紅黑樹取代。

[2-3 tree](http://en.wikipedia.org/wiki/2–3_tree) 可用 AA 樹取代。

## 活動簽到

[Bruce Tsai](/ep/profile/oLLqeaQgDjg)

[Carl Su](/ep/profile/n5euV0AaWLn)

[FourDollars](/ep/profile/tgNQRpN8EgG)

[Jonathan Hsieh](/ep/profile/v2IkzygwDuI)

[Manuel Stallman](/ep/profile/GgkcGJEol5r)

StarNight

[violetson](/ep/profile/oJusv72f72w)