數(shù)據結構可視化網站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
demo：https://github.com/lilingyan/take-TreeMap-apart
bst(二叉搜索樹)
在插入數(shù)據均勻分布時，就是折半查找
二叉搜索樹的定義
- 若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
- 若右子樹不空辩蛋，則右子樹上所有結點的值均大于它的根結點的值咬荷；
- 左劈猿、右子樹也分別為二叉排序樹白群；
- 沒有鍵值相等的節(jié)點。
- 插入:
- 從根節(jié)點開始郊愧，遞歸比較大小，直至葉子葉子節(jié)點井佑。
- 把新節(jié)點加上属铁。
- 從根節(jié)點開始郊愧，遞歸比較大小，直至葉子葉子節(jié)點井佑。
- 刪除:
- 從根節(jié)點開始，遞歸比較大小躬翁，直至key相等焦蘑。
- 如果該節(jié)點有兩個孩子，則用后繼節(jié)點的值替換它盒发，然后刪除后繼節(jié)點(后繼節(jié)點必然是葉子節(jié)點例嘱，執(zhí)行c)
- 如果只有一個子節(jié)點，則把該節(jié)點的父節(jié)點和該節(jié)點的子節(jié)點相互指向(這樣就沒有指向該節(jié)點的了宁舰，就刪除了)
- 如果是葉子節(jié)點蝶防，直接置空父節(jié)點指向改節(jié)點的指針
- 從根節(jié)點開始，遞歸比較大小躬翁，直至key相等焦蘑。
avl(平衡二叉樹)
BST在key值是線性的時候，就又變成一維的查找了(就是數(shù)組)明吩，AVL樹能極大的提高線性key的查詢效率
平衡二叉樹的定義
- 首先它是BST
- 左右子樹高度差不超過1(遞歸)
平衡
自底向上间学，一層一層的平衡，直到根印荔。
- 插入后情況
- 不需要調整
- 根節(jié)點或者左右子樹高度差小于1
- 需要調整(左右子樹高度差大于1)
- 左子樹高的情況(2)
- case1: 插入節(jié)點是左子節(jié)點的左子節(jié)點
- 右旋父節(jié)點
- case2:
- 把自己左旋
- 把原父節(jié)點右旋
- case1: 插入節(jié)點是左子節(jié)點的左子節(jié)點
- 右子樹高的情況(-2)
- 與上同理(鏡像)
- 左子樹高的情況(2)
- 不需要調整
- 刪除后情況
- 不需要調整
- 根節(jié)點或者左右子樹高度差小于1
- 需要調整(左右子樹高度差大于1)
- 左子樹高的情況(2)
- case1: 插入節(jié)點是左子節(jié)點的左子節(jié)點
- 當前節(jié)點右旋
- case1: 插入節(jié)點是左子節(jié)點的左子節(jié)點
- 當前節(jié)點右旋
- case2:
- 當前節(jié)點x左子節(jié)點左旋
- 當前節(jié)點右旋
- case1: 插入節(jié)點是左子節(jié)點的左子節(jié)點
- 右子樹高的情況(-2)
- 與上同理(鏡像)
- 左子樹高的情況(2)
- 不需要調整
