平衡二叉樹旋轉的結果不是唯一的,具體見下面分析:
插入序列:12, 4, 1, 7, 8, 10, 9, 2, 11, 6, 5
1、先插入12成為根
2、插入4在12的左子樹,沒有旋轉
3、插入1在4的左子樹,以4為中心向右單旋轉,結果如下:
4
/ \
1 12
4、插入7在12的左子樹,沒有旋轉
5、插入8在7的右子樹,以8開始先左後右雙旋轉,結果如下:
1 8
7 12
6、插入10在12左子樹,以8為中心開始向左單旋轉,結果如下:
8
4 12
/ \ /
1 7 10
7、插入9在10 的左子樹,以10為中心向右單旋轉,結果如下:
4 10
/ \ / \
1 7 9 12
8、插入2在1的右子樹,沒有旋轉
9、插入11在12 的左子樹,沒有旋轉
10、插入6在7的左子樹,沒有旋轉
11、插入5在6的左子樹,以6為中心向右單旋轉,結果如下:
1 6 9 12
\ / \ /
2 5 7 11
平衡二叉樹旋轉的結果不是唯一的,具體見下面分析:
插入序列:12, 4, 1, 7, 8, 10, 9, 2, 11, 6, 5
1、先插入12成為根
2、插入4在12的左子樹,沒有旋轉
3、插入1在4的左子樹,以4為中心向右單旋轉,結果如下:
4
/ \
1 12
4、插入7在12的左子樹,沒有旋轉
5、插入8在7的右子樹,以8開始先左後右雙旋轉,結果如下:
4
/ \
1 8
/ \
7 12
6、插入10在12左子樹,以8為中心開始向左單旋轉,結果如下:
8
/ \
4 12
/ \ /
1 7 10
7、插入9在10 的左子樹,以10為中心向右單旋轉,結果如下:
8
/ \
4 10
/ \ / \
1 7 9 12
8、插入2在1的右子樹,沒有旋轉
9、插入11在12 的左子樹,沒有旋轉
10、插入6在7的左子樹,沒有旋轉
11、插入5在6的左子樹,以6為中心向右單旋轉,結果如下:
8
/ \
4 10
/ \ / \
1 6 9 12
\ / \ /
2 5 7 11