# Data structure Note
## Basic Graph theorem
> 因為至少必須把從root到given vertex worst case有n個node 的input讀進來（skew BST)

>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
> $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數量

> 因為已經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
> 給定binary search tree(not binary tree)，就相當於有inorder traversal（有大小關係）

> 不是ADT, BST就是data structure

> 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)
> 
> 

---
> AVL 的**depth**差距可以超過2

> AVL tree insert $O(1)$ **rotation**, but $\theta(logn)$ **cost**

---
> insert到AVL tree要從下面往上check


## Splay tree
> 需要zig-zig & zig-zag & simple rotation

> concept: insert x, 找到x在BST中的parent, splay that parent，得到左右子樹，最後用x當root merge左右子樹

* amortized analysis
> Q: the $O(nlogn)$ part, how to go from amortized cost to actual cost?


## 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的情況）


* delete
>在traverse down的過程中，將看到的每一個node都變成紅色，由此可知，X的parent P會是紅色（因為從parent前進到X，所以parent一定已經被我們改成紅色），且sibling T會是黑色（因為parent紅色，child一定要是黑色不然會違反紅黑樹定義），改完X顏色為紅色之後再來做修正。


> top down insert and delete也可以轉成234 tree去做，再轉回來，個人覺得比較好做
> but how to 轉？


:::info
Buttom up Insert and Delete
:::




> buttom-up red black tree insert 最多需要 2個rotation

> delete rotate次數是 $O(1)$，但是recolor 次數會是 $O(logn)$
> but recolor fix up amortized $O(1)$

> any BST will do
key point: 先build balance binary search tree (recursively pick median as root）, 再上色變成red black tree

> BST不一定是 balanced,若要將BST轉成red black tree，先做 $O(n)$ inorder traversal，再將sorted array recursively pick median as root，轉成 balanced BST，再上色，得到red black tree

> 紅黑樹中number of nodes的最大比例 --> black : red = 1 : 2（每一個black node都有兩個red child)


## heap

## Binomial heap
Binomial heap insert amortize cost $O(1)$, worst case $O(logn)$

## Fibonacci heap





> ( c)：若rank9的child被cut, root會被mark(decrease key operation)，所以若之後有任何child被cut，root就會跟著被拔掉，不會再是root。
(d) : WTF
(e) ：就是c小題若再有child被cut的情況，r單獨為一個tree


## 2-3-4 Tree

* 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

http://www.cse.chalmers.se/edu/year/2018/course/DIT961/files/lectures/dit961_lecture_10.pdf

## AA tree





> 在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等等的修正






## Leftist heap & Skew heap


> 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


> skew heap merge worst case O(n), amortized O(logn)
> skew heap發明動機是因為不想maintain null path length等等資訊，就不管如何都直接switch sub trees


> 高度可以是 $O(N)$，但是因為operation都在right sub tree上進行，right sub tree 高度保證 $O(logn)$，所以operation cost worst case $O(logn)$


## Disjoint set
> yes, 就算是被path compression往上提到root，rank也不會變
rank只是height的近似值，initialize 0, 只在union時有可能被 +1(or不變)
trace code: https://en.wikipedia.org/wiki/Disjoint-set_data_structure


> Union by rank + path compression的 worst case依然是 $O(log n)$
> 

> rank 指的是 x的children數量(不含grand children即以下)

## Amortized analysis
> By Definition: $(O(n) * n) / n = O(n)$
---
> 單次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)$)



## hashing




## Treap
:::info
Treap = Tree + Heap
:::


## DEAP

## SMMH