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

旋轉範例


Hash

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

Collision 處理

  • Open addressing
    • Linear probing
Select a repo