初次學習資料結構和演算法是幾年前的事情了，當時遇到的困難沒有記錄下來，回過頭來復習，記錄下學習時遇到的問題，
平衡二叉樹（二叉搜索樹）（ALV樹）可以保證查詢效率，在此之前先學習二叉排序樹（BST —— Binary Sort Tree），
在高度為h的ALV樹中，最小節點數 S(h) = S( h - 1 ) + S( h - 2 ) + 1，對于h = 0，S(h) = 1；h = 1，S(h) = 2，
函式S(h)與斐波那契樹密切相關，下面給出指定樹高度時，最少節點的ALV樹：
摘自——《資料結構與演算法分析：c語言描述》
初次學習ALV旋轉時，總是糾結于 “ 旋轉 ” 二字上，想象它具體是如何旋轉的，在紙上涂涂畫畫感覺 “ 旋轉 ” 二字并不恰當，
插入結點有可能破壞平衡，旋轉的目的是結點插入后，能夠維持樹的平衡，此處不包含洗掉！！！洗掉假設為惰性洗掉
插入節點會導致某一個節點的左右子樹深度差為 2 ，只需要將這個最小的不平橫子樹調整為平衡即可
下面分別舉例 LL旋轉、RR旋轉、LR旋轉、RL旋轉 （有的地方分類時只分左旋轉、右旋轉和雙旋轉）
LL旋轉： 新節點的位置在最小不平衡的子樹的根節點的左孩子的左子樹
維持平衡的方式：
root的左孩子（黃色）替代root（紅色）的位置，不必關注具體指標的變化，理解節點的變化，指標的變化自然而然就出來了，
RR旋轉：新節點的位置在最小不平衡的子樹的根節點的右孩子的右子樹，與LL旋轉類似，不多贅述，
LR旋轉：新節點的位置在最小不平衡的子樹的根節點的左孩子的右子樹，
維持平衡的方式：讓root的左孩子的右孩子（藍色）取代root
RL旋轉：新節點的位置在最小不平衡的子樹的根節點的右孩子的左子樹，與LR旋轉類似，不多贅述，
本文來自博客園，作者：長壽奉孝，轉載請注明原文鏈接：https://www.cnblogs.com/tyt0o0/p/16676267.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/508093.html
標籤：其他
上一篇：基本資料結構