(1)聽插入12,聽这是第一个结点,是根结点.
(2)聽插入24,聽比12大,作为12的右分支.
聽聽聽聽12
聽聽聽聽聽\
聽聽聽聽聽聽24
(3)聽插入36,聽结点12的平衡因子BF变成-2(右子树过高),要左旋(逆时针旋转),
聽聽聽聽此时,结点24成为根结点.
聽聽聽聽平衡因子BF(Balance聽Factor)就是:
聽聽聽聽将二叉树上结点的聽左子树深度聽减去聽右子树深度的值.
聽聽聽聽12聽聽
聽聽聽聽聽\
聽聽聽聽聽聽24聽聽聽聽聽聽聽聽聽24
聽聽聽聽聽聽聽\聽聽聽聽聽聽聽聽/聽聽\
聽聽聽聽聽聽聽聽36聽聽聽聽聽12聽聽聽36聽
聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽左旋后
(4)聽插入90,聽结点24的BF是-1,二叉树仍然保持平衡.
聽聽聽聽聽聽24
聽聽聽聽聽/聽聽\
聽聽聽聽12聽聽聽36聽
聽聽聽聽聽聽聽聽聽聽\
聽聽聽聽聽聽聽聽聽聽聽90
(5)聽插入52,聽结点36的BF是-2,结点90的BF是+1,两个符号不一致,结点90和52先右旋,
聽聽聽聽此时,结点52的BF是-1,结点36的BF是-2,再对结点36,52,90进行左旋.
聽聽聽聽聽聽24聽聽聽聽聽聽聽聽聽聽聽聽聽24聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽24
聽聽聽聽聽/聽聽\聽聽聽聽聽聽聽聽聽聽聽/聽聽\聽聽聽聽聽聽聽聽聽聽聽聽聽聽/聽聽\
聽聽聽聽12聽聽聽36聽聽聽聽聽聽聽聽12聽聽聽36聽聽聽聽聽聽聽聽聽聽聽12聽聽聽52
聽聽聽聽聽聽聽聽聽聽\聽聽聽聽聽聽聽聽聽聽聽聽聽聽\聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽/聽\
聽聽聽聽聽聽聽聽聽聽聽90聽聽聽聽聽聽聽聽聽聽聽聽52聽聽聽聽聽聽聽聽聽聽聽聽聽聽36聽聽90
聽聽聽聽聽聽聽聽聽聽/聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽\
聽聽聽聽聽聽聽聽聽52聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽90
聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽右旋后聽聽聽聽聽聽聽聽聽聽聽聽聽左旋后
(6)聽插入30,聽结点52的BF是+1,结点24的BF是-2,两个符号不一致,
聽聽聽聽结点30,36和52先右旋,此时,结点36的BF是-1,结点24的BF是-2,
聽聽聽聽结点12,24和36进行左旋.
聽聽聽聽聽聽聽24聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽24聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽36
聽聽聽聽聽聽/聽聽\聽聽聽聽聽聽聽聽聽聽聽聽聽/聽聽\聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽/聽聽\
聽聽聽聽聽12聽聽聽52聽聽聽聽聽聽聽聽聽聽12聽聽聽36聽聽聽聽聽聽聽聽聽聽聽聽聽聽24聽聽聽52
聽聽聽聽聽聽聽聽聽聽/聽\聽聽聽聽聽聽聽聽聽聽聽聽聽聽/聽\聽聽聽聽聽聽聽聽聽聽聽聽/聽\聽聽聽聽\
聽聽聽聽聽聽聽聽聽36聽聽90聽聽聽聽聽聽聽聽聽聽聽30聽聽52聽聽聽聽聽聽聽聽聽12聽聽30聽聽聽90
聽聽聽聽聽聽聽聽/聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽\
聽聽聽聽聽聽聽30聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽90
聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽右旋后聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽左旋后
(7)聽插入41,聽二叉树仍然保持平衡.
聽聽聽聽聽聽聽聽聽聽36
聽聽聽聽聽聽聽聽/聽聽聽聽\
聽聽聽聽聽聽聽24聽聽聽聽52
聽聽聽聽聽聽/聽\聽聽聽聽/聽\
聽聽聽聽12聽聽30聽聽41聽聽90
(8)聽插入8,聽二叉树仍然保持平衡.
聽聽聽聽聽聽聽聽聽聽聽36
聽聽聽聽聽聽聽聽聽/聽聽聽聽\
聽聽聽聽聽聽聽聽24聽聽聽聽52
聽聽聽聽聽聽聽/聽\聽聽聽聽/聽\
聽聽聽聽聽12聽聽30聽聽41聽聽90
聽聽聽聽聽/
聽聽聽聽8
(9)聽插入10,聽结点8的BF是-1,结点12的BF是+2,结点24的BF是+2,
聽聽聽聽结点8和10先左旋,此时,结点10的BF是+1,结点12的BF是+2,
聽聽聽聽对结点10,8,12进行右旋.
聽聽聽聽聽聽聽聽聽聽聽36聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽36聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽36
聽聽聽聽聽聽聽聽聽/聽聽聽聽\聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽/聽聽聽聽\聽聽聽聽聽聽聽聽聽聽聽聽聽聽/聽聽聽聽聽\
聽聽聽聽聽聽聽聽24聽聽聽聽52聽聽聽聽聽聽聽聽聽聽聽聽聽聽24聽聽聽聽52聽聽聽聽聽聽聽聽聽聽聽聽24聽聽聽聽聽52
聽聽聽聽聽聽聽/聽\聽聽聽聽/聽\聽聽聽聽聽聽聽聽聽聽聽聽/聽\聽聽聽聽/聽\聽聽聽聽聽聽聽聽聽聽/聽\聽聽聽聽聽/聽\
聽聽聽聽聽12聽聽30聽聽41聽聽90聽聽聽聽聽聽聽聽12聽聽30聽聽41聽聽90聽聽聽聽聽聽聽10聽聽30聽聽41聽聽90
聽聽聽聽聽/聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽/聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽/聽\
聽聽聽聽8聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽10聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽8聽聽12
聽聽聽聽聽\聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽/
聽聽聽聽聽聽10聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽8
聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽左旋后聽聽聽聽聽聽聽聽聽聽聽聽聽聽右旋后
(10)聽插入38,聽二叉树仍然保持平衡.
聽聽聽聽聽聽聽聽聽聽聽聽聽聽36
聽聽聽聽聽聽聽聽聽聽/聽聽聽聽聽聽聽聽\
聽聽聽聽聽聽聽聽聽24聽聽聽聽聽聽聽聽52
聽聽聽聽聽聽聽聽/聽\聽聽聽聽聽聽聽/聽聽\
聽聽聽聽聽聽10聽聽聽30聽聽聽聽41聽聽90
聽聽聽聽聽聽/聽\聽聽聽聽聽聽聽/
聽聽聽聽聽8聽聽12聽聽聽聽聽38
(11)聽插入61,聽二叉树仍然保持平衡.
聽聽聽聽聽聽聽聽聽聽聽聽聽聽36
聽聽聽聽聽聽聽聽聽聽/聽聽聽聽聽聽聽聽\
聽聽聽聽聽聽聽聽聽24聽聽聽聽聽聽聽聽52
聽聽聽聽聽聽聽聽/聽\聽聽聽聽聽聽聽/聽聽\
聽聽聽聽聽聽10聽聽聽30聽聽聽聽41聽聽90
聽聽聽聽聽聽/聽\聽聽聽聽聽聽聽/聽聽聽聽/
聽聽聽聽聽8聽聽12聽聽聽聽聽38聽聽聽61
聽聽聽聽这就是最后得到的平衡二叉树
聽聽
二叉树的总结点数聽N=11
如果假设每个元素查找概率相同,平均查找长度是聽log2(N)=log2(11),
表示以2为底,取11的对数. |
转播
