數(shù)據(jù)結(jié)構(gòu)可視化網(wǎng)站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
demo：https://github.com/lilingyan/take-TreeMap-apart

bst(二叉搜索樹)

在插入數(shù)據(jù)均勻分布時，就是折半查找

二叉搜索樹的定義

1. 若左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；
2. 若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；
3. 左、右子樹也分別為二叉排序樹；
4. 沒有鍵值相等的節(jié)點。

• 插入:
  • 從根節(jié)點開始，遞歸比較大小，直至葉子葉子節(jié)點。
    1. 把新節(jié)點加上。
• 刪除:
  • 從根節(jié)點開始，遞歸比較大小，直至key相等。
    1. 如果該節(jié)點有兩個孩子，則用后繼節(jié)點的值替換它，然后刪除后繼節(jié)點(后繼節(jié)點必然是葉子節(jié)點，執(zhí)行c)
    2. 如果只有一個子節(jié)點，則把該節(jié)點的父節(jié)點和該節(jié)點的子節(jié)點相互指向(這樣就沒有指向該節(jié)點的了，就刪除了)
    3. 如果是葉子節(jié)點，直接置空父節(jié)點指向改節(jié)點的指針

avl(平衡二叉樹)

BST在key值是線性的時候，就又變成一維的查找了(就是數(shù)組)，AVL樹能極大的提高線性key的查詢效率

平衡二叉樹的定義

1. 首先它是BST
2. 左右子樹高度差不超過1(遞歸)

平衡
自底向上，一層一層的平衡，直到根。

• 插入后情況
  • 不需要調(diào)整
    1. 根節(jié)點或者左右子樹高度差小于1
  • 需要調(diào)整(左右子樹高度差大于1)
    1. 左子樹高的情況(2)
       • case1: 插入節(jié)點是左子節(jié)點的左子節(jié)點
         1. 右旋父節(jié)點
       • case2:
         1. 把自己左旋
         2. 把原父節(jié)點右旋
    2. 右子樹高的情況(-2)
       • 與上同理(鏡像)
• 刪除后情況
  • 不需要調(diào)整
    1. 根節(jié)點或者左右子樹高度差小于1
  • 需要調(diào)整(左右子樹高度差大于1)
    1. 左子樹高的情況(2)
       • case1: 插入節(jié)點是左子節(jié)點的左子節(jié)點
         1. 當(dāng)前節(jié)點右旋
       • case1: 插入節(jié)點是左子節(jié)點的左子節(jié)點
         1. 當(dāng)前節(jié)點右旋
       • case2:
         1. 當(dāng)前節(jié)點x左子節(jié)點左旋
         2. 當(dāng)前節(jié)點右旋
    2. 右子樹高的情況(-2)
       • 與上同理(鏡像)