---
# System prepended metadata

title: DS Final

---

# DS Final 

## Graph

### Shorst path
* Floyd-Warshall
    * with positive or negative edge weights (but with no negative cycles)
* Bellman
    * with positive or negative edge weights , and it can check if negative cycles exist or not.
## RB-tree
* node非黑即紅
* root是黑色的
* 每個leaf (external node, or nil)都是黑色
* 如果一個node是紅的, 則它的children都是黑的
* 每一條由root到leaf上的path擁有相同數量的black edges

### 旋轉範例
![](https://i.imgur.com/Ka2OWtN.png)
![](https://i.imgur.com/ND7uQ9V.png)

## Hash 

* hash function : 把key對應到一個數值
* collision: 要把資料存進某櫃子的時候, 該櫃子已經有東西了
* overflow:要把資料存進某櫃子的時候, 該櫃子已經滿了

Collision 處理
* Open addressing
    *  Linear probing 