《平衡二叉树构建过程之我的理解》由会员分享，可在线阅读，更多相关《平衡二叉树构建过程之我的理解（7页珍藏版）》请在金锄头文库上搜索。
1、平衡二叉树构建过程之我的理解 平衡二叉查找树 构建方法 郭建勇 定义 平衡二叉树(全称平衡二叉查找树) 是一棵二叉树 是一颗二叉查找树（对于任意节点x,其左子树的所有节点都小于x,x的右子树的节点都大 于等于x) 是一颗平衡树,平衡意思是对于任意节点，其左子树高度和右子树高度相差不超过,左右 子树的高度差称为平衡因子a,也即| 辨析 平衡二叉树s二叉查找树 二叉查找树也称作二叉排序树或者二叉搜索树平衡二叉树的本质特点是左右子树的平衡,而二叉查找树是不要求平衡的 这也是为什么二叉搜索树在某些极端情况下搜索效率很低的原因:高度太高，接近线性效率 平衡二叉树就是为了尽量降低树的高度而提出来的. 插入
2、 平衡二叉树的查找逻辑比较简单，这里不讲了 构建平衡二叉树时的逻辑需要深刻理解插入节点时如果左右子树平衡就不需要调整节点 如果左右不平衡那么就需要调整节点 由于不平衡没有一个统一的调整策略，需要分情况看待,左左，右右,左右，右左 出现不平衡-右右 100 110 . 10. 12. ew 右右不平衡: 首先定位最小不平衡二叉树，以10为根节点的树 如果新插入节点ew是在00的右孩子(10）的右子树分支(以12为根的子树)就称为右右不平衡 10 . 105. 0. ew 思路: 把100的右子树高度降低1,或者把1的左子树高度加1 如果能把0为根的树提高到00的位置,那么右子树高度就降低了 10
3、 . 0. 105. ew 步骤1： 把110的左子树砍掉，此时11没有右子树了,如图黑色部分是被暂时挪走的部分 010 0 . . 15. ew 步骤： 把10以及其左子树也砍掉，并且把10为根的树拔高一个等级,用替代原来10的位置,11成为树根 110 1120. . 05. nw 步骤1： 把1为根的左子树部分对接到10的左子树位置,因为之前的步骤里已经保证0的左子树是空的,所以可以挪过来 10 0020. 105 . . new 步骤： 把105的re对接到100的右子树位置,因为100之前的右子树是110，分离之后肯定是空的.所以可以对接上去 右右:调整过程 11 120. 15 .
4、 . ne 完毕 至此，右右调整已经结束,如何证明调整后是平衡树呢上提了一个节点，所以120ree的高度降低了,0tree降低了一个层次，所以高度增加了.所以肯定是平衡的 如果某个子树是空的，那么最多是调整没有得到降低或者增加,但是由于不会是个子树都是空的，所以至少有一个增加了或者另外一个降低了,所以仍然是平衡的 110 . 10. 20. ew 右左不平衡： 这种类型的不平衡就是最小不平衡二叉树的右子树的左子树部分插入形成的不平衡 . 15. 10. ne 思路: 解决右左不平衡的思路是:先转化为右右不平衡再用右右调整方法调整所以重点是：右左-右右 110 . 05a b 12. w 右左-
5、右右: 110 . 提升一个层次 105a 120. new 右左-右右： 10 . 15 b 120. new 对接到合适位置 右左-右右： 05 . a 110 b 2. new 右左-右右: 把5的右子树砍掉,也就是黄色的-new部分砍掉，这样15就没有右子树了把红色的10以及其左子树整体提升到100的右子树 10 . 10 10 b . ew 右左-右右: 把绿色的110整体对接到1的右子树上, 105 . a 10 b 12. new 右左-右右: 把黄色的部分bnew对接到合适的位置，哪里合适呢。原来是105的右孩子，所以b肯定大于105， 10原来是10的左孩子,所以11010b
6、，也即b肯定小于11,而且10的左孩子原来是05,切割之后110的左孩子肯定是空的,所以b的合适位置就是110的左孩子变换完毕 105 . a 110 120. e 右左-右右： 为什么这样变换后是把右左改变为右右不平衡了呢假设1的左子树高度是n 由于是不平衡，10的右子树高度肯定是+2 105 .a110 b12 . new 右左-右右: 100.右.左高度是n+ 10右.右高度肯定是n+1，因为如果是 105 .a110 b20 . new 右左-右右: 由于红色部分原来高度最大可能是n2,变换后提升了一个层次,必然 105 .a10 b20 . new 变换为右右不平衡 至此已经把右左不平衡转换为了右右不平衡 左左不平衡：是右右不平衡左右对称调换的解决方法 左右不平衡：首先转变为左左不平衡，然后用左左解决方法 第 1 页 共 1 页免责声明：图文来源于网络搜集，版权归原作者所以若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。
