owned this note
owned this note
Published
Linked with GitHub
# Data structure Note
## Basic Graph theorem
![](https://i.imgur.com/J9HK5kj.png)
> 因為至少必須把從root到given vertex worst case有n個node 的input讀進來(skew BST)
![](https://i.imgur.com/XARFbY8.png)
>recursive DFS handle the first child first(in the adjacency list)
>non-recursive DFS handle the last child first(in the adjacency list)
## Time Complexity
![](https://i.imgur.com/ln5QvA8.png)
> $lg^{*}(2^n) = 1 + lg^{*}(n)$
## Sorting
> strait radix sort 從 the lowest digit開始,radix exchange從the highest digit開始,且使用類似quicksort的partition。time complexity都是 $O(bn)$, where b is digit數量
![](https://i.imgur.com/M9PMHGF.png)
![](https://i.imgur.com/GBD26ZP.png)
> 因為已經sorted,所以找到median是$O(1)$, $T(n) = 2T(n/2) + O(1)$, 根據master theorem, total time complexity 為 $O(n)$。
若不是sorted,order statistic 找median是$O(n)$,$T(n) = 2T(n/2) + O(n)$,total time complexity 為 $O(nlgn)$,沒有違背comparison model sorting的lower bound。
## Linked list
* 改變的pointer數量
| | singly liked list | doubly liked list |
| -------- | -------- | -------- |
| insert | 2 | 4 |
| delete | 1 | 2 |
## Binary tree traversal & construction
![](https://i.imgur.com/8RBTnyD.png)
> 給定binary search tree(not binary tree),就相當於有inorder traversal(有大小關係)
![](https://i.imgur.com/DlAtMmD.png)
> 不是ADT, BST就是data structure
![](https://i.imgur.com/HTQkavs.png)
![](https://i.imgur.com/tUUakpE.png)
> binary search是$O(lgn)$, $O(n)$ is not tight bound,但是根據定義這句話並沒有錯。
## AVL tree
* Traverse: amortized $\theta(n)$, because tree of $n$ nodes has $n-1$ edge, we traverse each edge exactly twice, so amortized cost is : $2*(n-1) / n$
tree height : $1.44*log(n)$
min # node: $F_{k+2} - 1$, where $F_k$ is the Kth Fibonacci number
max # node: $2^h -1$ (perfect BST)
> ![](https://i.imgur.com/6nN83tf.jpg)
> ![](https://i.imgur.com/FWAQ9Qi.png)
---
![](https://i.imgur.com/Ep7nzn7.png)
> AVL 的**depth**差距可以超過2
![](https://i.imgur.com/W5iv6rB.png)
> AVL tree insert $O(1)$ **rotation**, but $\theta(logn)$ **cost**
---
![](https://i.imgur.com/6zYNMes.png)
![](https://i.imgur.com/JyZ0vSX.png)
> insert到AVL tree要從下面往上check
![](https://i.imgur.com/fNEFV0n.png)
## Splay tree
![](https://i.imgur.com/v6CQOEZ.png)
> 需要zig-zig & zig-zag & simple rotation
![](https://i.imgur.com/O4dZC6y.png)
> concept: insert x, 找到x在BST中的parent, splay that parent,得到左右子樹,最後用x當root merge左右子樹
* amortized analysis
![](https://i.imgur.com/PlkDpKT.png)
![](https://i.imgur.com/5WWGOWC.png)
![](https://i.imgur.com/dCK9USV.png)
![](https://i.imgur.com/kwmAhOU.png)
![](https://i.imgur.com/xIVsyGi.png)
![](https://i.imgur.com/OoOmxK3.png)
![](https://i.imgur.com/lL0V4w8.png)
> Q: the $O(nlogn)$ part, how to go from amortized cost to actual cost?
![](https://i.imgur.com/kebItjw.png)
![](https://i.imgur.com/s2rJkTn.png)
## Red Black tree
tree height h: $lgn <= h <= 2lgn$,this bound is not tight。
:::info
Top Down Insert and Delete
:::
> Slides: https://www.slideshare.net/piotrszymanski/red-black-trees#btnNext
> https://cseweb.ucsd.edu/classes/su05/cse100/cse100Midterm1Solutions.pdf
* Insert
> Top down的時候,只有以下這個case會需要特別處理,也就是要往下前進到X時,X的兩個child都是紅色的
>核心想法:想辦法讓黑色node下移,同時維持black height for each path,之後才不會發生insert new node到一個red node之下(造成連續兩個red node的情況)
![](https://i.imgur.com/JWZdw8l.png)
![](https://i.imgur.com/y5HCwHs.png)
![](https://i.imgur.com/KaRQGij.png)
![](https://i.imgur.com/GLJ8q62.png)
![](https://i.imgur.com/7pJaGEY.png)
* delete
>在traverse down的過程中,將看到的每一個node都變成紅色,由此可知,X的parent P會是紅色(因為從parent前進到X,所以parent一定已經被我們改成紅色),且sibling T會是黑色(因為parent紅色,child一定要是黑色不然會違反紅黑樹定義),改完X顏色為紅色之後再來做修正。
![](https://i.imgur.com/Ab6pIqi.png)
![](https://i.imgur.com/hykup3E.png)
![](https://i.imgur.com/XhZZKpW.png)
![](https://i.imgur.com/1lfShCm.png)
![](https://i.imgur.com/GvsKqQ4.png)
![](https://i.imgur.com/XqA2CUu.png)
![](https://i.imgur.com/06Rkliu.png)
![](https://i.imgur.com/Pbm5DB0.png)
![](https://i.imgur.com/tsbl8Qw.png)
> top down insert and delete也可以轉成234 tree去做,再轉回來,個人覺得比較好做
> but how to 轉?
![](https://i.imgur.com/EKrsqoC.png)
![](https://i.imgur.com/Dbr74av.png)
![](https://i.imgur.com/XYp4iL4.png)
![](https://i.imgur.com/G7mAJxv.png)
![](https://i.imgur.com/m7Leicc.png)
![](https://i.imgur.com/t6BVod9.png)
![](https://i.imgur.com/8aqrlPe.png)
![](https://i.imgur.com/4rx1DzG.png)
![](https://i.imgur.com/T1nMW73.png)
:::info
Buttom up Insert and Delete
:::
![](https://i.imgur.com/e9aQI2B.jpg)
![](https://i.imgur.com/1sxMArl.png)
![](https://i.imgur.com/PhM1n2B.png)
![](https://i.imgur.com/xN3J5LM.png)
![](https://i.imgur.com/XEZlSGt.jpg)
![](https://i.imgur.com/HH8PBMy.jpg)
![](https://i.imgur.com/Sa4Lwzi.png)
> buttom-up red black tree insert 最多需要 2個rotation
![](https://i.imgur.com/SMeDitB.png)
![](https://i.imgur.com/iJvfAMC.jpg)
> delete rotate次數是 $O(1)$,但是recolor 次數會是 $O(logn)$
> but recolor fix up amortized $O(1)$
![](https://i.imgur.com/S0cmAuH.png)
![](https://i.imgur.com/slL1LyY.png)
> any BST will do
key point: 先build balance binary search tree (recursively pick median as root), 再上色變成red black tree
![](https://i.imgur.com/KQpZPLO.png)
> BST不一定是 balanced,若要將BST轉成red black tree,先做 $O(n)$ inorder traversal,再將sorted array recursively pick median as root,轉成 balanced BST,再上色,得到red black tree
![](https://i.imgur.com/76KO5iW.png)
> 紅黑樹中number of nodes的最大比例 --> black : red = 1 : 2(每一個black node都有兩個red child)
![](https://i.imgur.com/mAUnibW.png)
## heap
![](https://i.imgur.com/IUYFfPN.png)
![](https://i.imgur.com/kubrpS6.png)
## Binomial heap
Binomial heap insert amortize cost $O(1)$, worst case $O(logn)$
![](https://i.imgur.com/NjzEcaA.png)
## Fibonacci heap
![](https://i.imgur.com/INe41KL.png)
![](https://i.imgur.com/XclzbdA.png)
![](https://i.imgur.com/Uc4wi3A.png)
![](https://i.imgur.com/wkAFUBr.png)
![](https://i.imgur.com/sfbzdNb.png)
![](https://i.imgur.com/h3UsHRh.png)
![](https://i.imgur.com/LKlEArl.png)
![](https://i.imgur.com/yNCoZJd.png)
![](https://i.imgur.com/3rdIG4p.png)
![](https://i.imgur.com/nIc0ems.png)
![](https://i.imgur.com/bHwBgEj.png)
![](https://i.imgur.com/WXTMLsk.png)
![](https://i.imgur.com/Dx4Ip5G.png)
![](https://i.imgur.com/sTtLmZY.png)
![](https://i.imgur.com/reL6Nwq.png)
![](https://i.imgur.com/9gcq1BK.png)
![](https://i.imgur.com/xUIstLk.png)
![](https://i.imgur.com/6H2quxp.png)
> ( c):若rank9的child被cut, root會被mark(decrease key operation),所以若之後有任何child被cut,root就會跟著被拔掉,不會再是root。
(d) : WTF
(e) :就是c小題若再有child被cut的情況,r單獨為一個tree
![](https://i.imgur.com/NlfF07Z.png)
![](https://i.imgur.com/gsJR11Q.png)
![](https://i.imgur.com/bnjp3sA.png)
## 2-3-4 Tree
![](https://i.imgur.com/8MWlXQK.png)
* 234 tree insert & delete fix up work(not actual cost) amortized $O(1)$, actual cost amortized is still $O(logn)$
> https://web.stanford.edu/class/archive/cs/cs166/cs166.1146/lectures/05/Small05.pdf
* 23 tree top down :https://www.ptt.cc/bbs/Grad-ProbAsk/M.1548570005.A.531.html
![](https://i.imgur.com/TofQPDF.png)
http://www.cse.chalmers.se/edu/year/2018/course/DIT961/files/lectures/dit961_lecture_10.pdf
## AA tree
![](https://i.imgur.com/rQZ3Axt.png)
![](https://i.imgur.com/oQeyeRn.png)
![](https://i.imgur.com/JDXGPmI.png)
![](https://i.imgur.com/hi0ygCW.png)
![](https://i.imgur.com/3oJzaTG.png)
![](https://i.imgur.com/spsczpg.png)
![](https://i.imgur.com/asB452p.png)
![](https://i.imgur.com/kmf8W7a.png)
![](https://i.imgur.com/l7nES7C.png)
![](https://i.imgur.com/G4mn4yq.png)
![](https://i.imgur.com/QOiXzLw.png)
![](https://i.imgur.com/pGBVptF.png)
![](https://i.imgur.com/LfMR2KC.png)
![](https://i.imgur.com/FdJ0hku.png)
> 在deletion中,有兩種情況會需要decrease 一個node的level
> 第一種是此node的兩個child只要有一個比自己低兩level以上就會要decrease level
> 第二種情況是你是第一種情況中node的 right horizontal child
> decrease level後要先解決skew split之後才可以往上到Parent(Buttom up),看看parent有沒有需要decrease level, skew split等等的修正
![](https://i.imgur.com/9l4ZSCm.png)
![](https://i.imgur.com/Y77co38.png)
![](https://i.imgur.com/hs9EYJs.png)
![](https://i.imgur.com/NSgwiNd.png)
![](https://i.imgur.com/UtlpR7x.png)
![](https://i.imgur.com/l0ZLANo.png)
![](https://i.imgur.com/dgJh72c.png)
![](https://i.imgur.com/PdnQPXN.png)
![](https://i.imgur.com/hSczfui.png)
![](https://i.imgur.com/SP9SCDJ.png)
![](https://i.imgur.com/wEbbd7C.png)
![](https://i.imgur.com/WuDVkl9.png)
![](https://i.imgur.com/NcFmiNk.png)
![](https://i.imgur.com/REMOHmZ.png)
![](https://i.imgur.com/hiNRdNK.png)
![](https://i.imgur.com/CTIjzjx.png)
![](https://i.imgur.com/nZnlN2c.png)
![](https://i.imgur.com/Ov4U9vf.png)
![](https://i.imgur.com/0Pf6YWb.png)
## Leftist heap & Skew heap
![](https://i.imgur.com/pGhqJsH.png)
> leftist heap :
https://courses.cs.washington.edu/courses/cse326/08sp/lectures/markup/05-leftist-heaps-markup.pdf
> leftist heap merge worst case O(logn)(perform all work on right sub tree)
>leftist heap decrease key: https://courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture19/sld001.htm
>leftist heap:
>https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/heaps.pdf
> skew heap : https://courses.cs.washington.edu/courses/cse326/08sp/lectures/markup/06-skew-heaps-markup.pdf
![](https://i.imgur.com/NDpJn9B.png)
> skew heap merge worst case O(n), amortized O(logn)
> skew heap發明動機是因為不想maintain null path length等等資訊,就不管如何都直接switch sub trees
![](https://i.imgur.com/YL1TVrC.png)
![](https://i.imgur.com/VEEIqaB.png)
> 高度可以是 $O(N)$,但是因為operation都在right sub tree上進行,right sub tree 高度保證 $O(logn)$,所以operation cost worst case $O(logn)$
![](https://i.imgur.com/nBNyyXf.png)
![](https://i.imgur.com/YC6gu7i.png)
## Disjoint set
![](https://i.imgur.com/ZPnwlZY.png)
> yes, 就算是被path compression往上提到root,rank也不會變
rank只是height的近似值,initialize 0, 只在union時有可能被 +1(or不變)
trace code: https://en.wikipedia.org/wiki/Disjoint-set_data_structure
![](https://i.imgur.com/0c2KvEk.png)
![](https://i.imgur.com/qvboe3V.png)
![](https://i.imgur.com/HaTtd1K.png)
![](https://i.imgur.com/iHUlSxL.png)
> Union by rank + path compression的 worst case依然是 $O(log n)$
> ![](https://i.imgur.com/E7DQZAt.png)
![](https://i.imgur.com/vHBupyo.png)
![](https://i.imgur.com/kqau3kD.png)
> rank 指的是 x的children數量(不含grand children即以下)
## Amortized analysis
![](https://i.imgur.com/lxVZjHw.png)
> By Definition: $(O(n) * n) / n = O(n)$
---
![](https://i.imgur.com/7MQJiTW.png)
> 單次best case可以到 $\theta (1)$
> 單次worst case不會超過 n 次 amortized的time complexity
> 像是 Fibonacci heap decrease key 單次 worst case $O(n)$
> n 次操作amortized 也是 $O(n)$(Fibonacci heap decrease key amortized $O(1)$)
![](https://i.imgur.com/cxQ6RnK.png)
![](https://i.imgur.com/xT1QWhI.png)
## hashing
![](https://i.imgur.com/80CRP0p.png)
![](https://i.imgur.com/HuiYUzy.png)
![](https://i.imgur.com/L9k6pLt.png)
![](https://i.imgur.com/yCDi5Ya.png)
![](https://i.imgur.com/cFCFBYY.png)
![](https://i.imgur.com/2mbXJqG.png)
![](https://i.imgur.com/ntaN3X6.png)
![](https://i.imgur.com/4YRKfVI.png)
![](https://i.imgur.com/CMIRi8t.png)
![](https://i.imgur.com/htaQnRw.png)
![](https://i.imgur.com/mHnOMo7.png)
![](https://i.imgur.com/VIMucOk.png)
## Treap
:::info
Treap = Tree + Heap
:::
![](https://i.imgur.com/tF2HU26.png)
![](https://i.imgur.com/QnOJVjA.png)
![](https://i.imgur.com/1lgGymc.png)
![](https://i.imgur.com/rOyLCGx.png)
![](https://i.imgur.com/CHhOlUi.png)
## DEAP
## SMMH