选取一组数据分别为2,1,0,3,4,5,6,9,8,7的10个结点来构造平衡二叉树。
(1)首先数据为2的结点作为根结点插入,接着插入1,仍是平衡的,再插入0是,2的平衡因子变为2,此时出现了不平衡,因此需要进行调整,最低不平衡结点为2,属于LL型,根据上述网址的内容,则调整过程如图1所示。

20150819214905762.png

图 1

(2)接着插入3,是平衡的,再插入4,此时出现了不平衡,结点 1 和 2 的平衡因子都为 -2,结点2为最低不平衡结点,属于RR型,调整过程如图2所示。

20150819215824541.png

图 2

(3)接着插入5,此时结点 1 的平衡因子为 -2,导致不平衡,结点1为最低不平衡结点,属于RR型,调整如图3所示。

20150819221034665.png

图 3

(4)接着插入6,此时结点4的平衡因子为 -2,导致不平衡,结点4为最低不平衡结点,属于RR型,调整如图4所示。

20150819221925912.png

图 4

(5)接着插入9,是平衡的,再插入8,此时结点 3、5、6 的平衡因子都为 -2,导致不平衡,结点6为最低不平衡结点,属于RL型,调整如图5所示。

20150819222910676.png

图 5

(6)插入7,此时结点3、5的平衡因子为 -2,导致不平衡,最低不平衡结点为5,属于RL型,调整如图6所示。

20150819224654918.png

转自 吴小宝的博客

图 6