数据结构,将下列序列构造（55,31,11.37,46,73,63,2,7）平衡二叉树?

Question

数据结构,将下列序列构造（55,31,11.37,46,73,63,2,7）平衡二叉树?

Answer 1

1、空树,插入55,为根,无旋转
2、插入31,为55左子树,无旋转
3、插入11,为31左子树,发生向右的单旋转,结果31根、11左子树、55右子树
4、插入37,为55左子树,无旋转
5、插入46,为37右子树,发生先左后右双旋转,结果46为31的右子树根,37为46左子树,55为46右子树
6、插入73,为55右子树,发生向左单旋转,结果46变成根,31为左子树根、55为右子树根
7、插入63,为73左子树,发生先右后左双旋转,结果63变成46的右子树根,55为63的左子树、73为63的右子树
8、插入2,为11的左子树,无旋转
9、插入7,为2的右子树,发生先左后右双旋转,结果7变成31的左子树根,2为7的左子树,11为7的右子树
 
最终结果：