B Tee 與 Binary Search Tree

 參考：Fundamentals of data structure in C / Horowitz / 原文版 / ISBN 0-7167-8250-2 / 1993

1. Tree 的定義在p.187

2. 任何 tree 都可以被轉成 binary tree (fig 5.5, 5.6)

3. binary tree 每個 node 的 child 不超過 2

4. binary tree definition: p. 191

5. binary tree 可以為空樹；但 tree 不可為空樹

6. binary tree 兩個特型：skewed tree, complete binary tree

7. thread binary tree : 利用數量太多的 null link, p.211

8. Heap : 一個 complete binary tree 的特型

9. Max Heap 可以在 insert 與 delete 都取得 O (log n) 的效率。其他的 array or list 只能單邊達到 O(1) 另一邊是 O(n)

10. binary search tree 定義在 p.226

    是 binary tree 的一種

11. 依我看來，我們 source 裡的 tree 很有可能是 binary search tree

    它的規則總是：對一個 node 來說，它的 left node 比它小；它的 right node 比它大

12. p.228, p.230 有介紹 insert / delete of binary search tree.

註：從書中看，B tree 每個 node 的值有可能是一個或兩個。我想 source 中的 tree 應該不是 B tree.