平衡二叉树构建过程之我的理解

平衡二叉查找树

构建方法

郭建勇coolkissmile@gmail.com

定义

•平衡二叉树（全称平衡二叉查找树）

–是一棵二叉树

–是一颗二叉查找树（对于任意节点x，其左子树的所有节点都小于x，x的右子树的节点都大

于等于x）

–是一颗平衡树，平衡意思是对于任意节点，其左子树高度和右子树高度相差不超过1，左右

子树的高度差称为平衡因子a，也即|a|

辨析

•平衡二叉树vs二叉查找树

二叉查找树也称作二叉排序树或者二叉搜索树平衡二叉树的本质特点是左右子树的平衡，而二叉查找树是不要求平衡的

这也是为什么二叉搜索树在某些极端情况下搜索效率很低的原因：高度太高，接近线性效率

平衡二叉树就是为了尽量降低树的高度而提出来的.

插入

•平衡二叉树的查找逻辑比较简单，这里不讲了

•构建平衡二叉树时的逻辑需要深刻理解•插入节点时如果左右子树平衡就不需要调整节点

•如果左右不平衡那么就需要调整节点

•由于不平衡没有一个统一的调整策略，需要分情况看待，左左，右右，左右，右左.

出现不平衡--右右

100

110

...

105...

120...

new

右右不平衡：

首先定位最小不平衡二叉树，以100为根节点的树

如果新插入节点new是在100的右孩子（110）的右子树分支（以120为根的子树）就称为右右不平衡

110

...

105...

120...

new

思路：

把100的右子树高度降低1，或者把100的左子树高度加1

如果能把110为根的树提高到100的位置，那么右子树高度就降低了1

110

...

120...

105...

new

步骤1：