平衡二叉查找树
构建方法
郭建勇 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:
把110的左子树砍掉, 此时110没有右子树了, 如图黑色部分是被暂时挪走的部分
100110
120
. . .
...
105...
new
步骤1:
把100以及其左子树也砍掉, 并且把110为根的树拔高一个等级, 用110替代原来100的位置, 110成为树根
110
100120...
. . .
105...
new
步骤1:
把100为根的左子树部分对接到110的左子树位置, 因为之前的步骤里已经保证110的左子树是空的, 所以可以挪过来
110
100120...
105
. . .
...
new
步骤1:
把105的tree 对接到100的右子树位置, 因为100之前的右子树是110, 分离之后肯定是空的. 所以可以对接上去
右右 : 调整过程
110
100120...
105
. . .
...
new
完毕
至此, 右右调整已经结束, 如何证明调整后是平衡树呢110上提了一个节点, 所以120tree 的高度降低了1 , 100tree 降低了一个层次, 所以高度增加了1. 所以肯定是平衡的
如果某个子树是空的, 那么最多是调整没有得到降低或者增加, 但是由于不会是2个子树都是空的, 所以至少有一个增加了或者另外一个降低了, 所以仍然是平衡的
110
. . .
105...
120...
new
右左不平衡:
这种类型的不平衡就是最小不平衡二叉树的右子树的左子树部分插入形成的不平衡
110
. . .
105...
120...
new
思路:
解决右左不平衡的思路是: 先转化为 右右不平衡再用右右调整方法调整所以重点是: 右左--> 右右
110
. . .
105A
B
120...
new
右左--> 右右:
110
. . .
提升一个层次
105A
B
120...
new
右左--> 右右:
110
. . .
105A
B
120...
new
对接到合适位置
右左--> 右右:
105
. . .
A
110
B
120...
new
右左--> 右右:
把105的右子树砍掉, 也就是黄色的B-new 部分砍掉, 这样105就没有右子树了 把红色的105以及其左子树整体提升到100的右子树
105
. . .
A
110
120
B
...
new
右左--> 右右:
把绿色的110 整体对接到 105的右子树上,
105
. . .
A
110
B
120...
new
右左--> 右右:
把黄色的部分B-new 对接到合适的位置, 哪里合适呢? B 原来是105的右孩子, 所以B 肯定大于105,
105 原来是 110的左孩子, 所以 110>105>B, 也即 B肯定小于110, 而且110的左孩子原来是105, 切割之后110的左孩子肯定是空的, 所以B 的合适位置就是110的左孩子变换完毕
105
. . .
A
110
B
120...
new
右左--> 右右:
为什么这样变换后是把右左改变为右右不平衡了呢假设100的左子树高度是n
由于是不平衡, 100 的右子树高度肯定是 n+2
105
. . . A 110
B 120
...
new
右左--> 右右:
100.右. 左 高度是 n+2
100.右. 右 高度肯定是 n+1, 因为如果是
105
. . . A 110
B 120
...
new
右左--> 右右:
由于红色部分原来高度最大可能是N+2, 变换后提升了一个层次, 必然
105
. . . A 110
B 120
...
new
变换为 右右不平衡
至此已经把右左不平衡转换为了右右不平衡
左左不平衡: 是右右不平衡左右对称调换的解决方法
左右不平衡: 首先转变为左左不平衡 , 然后用左左解决方法
平衡二叉查找树
构建方法
郭建勇 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:
把110的左子树砍掉, 此时110没有右子树了, 如图黑色部分是被暂时挪走的部分
100110
120
. . .
...
105...
new
步骤1:
把100以及其左子树也砍掉, 并且把110为根的树拔高一个等级, 用110替代原来100的位置, 110成为树根
110
100120...
. . .
105...
new
步骤1:
把100为根的左子树部分对接到110的左子树位置, 因为之前的步骤里已经保证110的左子树是空的, 所以可以挪过来
110
100120...
105
. . .
...
new
步骤1:
把105的tree 对接到100的右子树位置, 因为100之前的右子树是110, 分离之后肯定是空的. 所以可以对接上去
右右 : 调整过程
110
100120...
105
. . .
...
new
完毕
至此, 右右调整已经结束, 如何证明调整后是平衡树呢110上提了一个节点, 所以120tree 的高度降低了1 , 100tree 降低了一个层次, 所以高度增加了1. 所以肯定是平衡的
如果某个子树是空的, 那么最多是调整没有得到降低或者增加, 但是由于不会是2个子树都是空的, 所以至少有一个增加了或者另外一个降低了, 所以仍然是平衡的
110
. . .
105...
120...
new
右左不平衡:
这种类型的不平衡就是最小不平衡二叉树的右子树的左子树部分插入形成的不平衡
110
. . .
105...
120...
new
思路:
解决右左不平衡的思路是: 先转化为 右右不平衡再用右右调整方法调整所以重点是: 右左--> 右右
110
. . .
105A
B
120...
new
右左--> 右右:
110
. . .
提升一个层次
105A
B
120...
new
右左--> 右右:
110
. . .
105A
B
120...
new
对接到合适位置
右左--> 右右:
105
. . .
A
110
B
120...
new
右左--> 右右:
把105的右子树砍掉, 也就是黄色的B-new 部分砍掉, 这样105就没有右子树了 把红色的105以及其左子树整体提升到100的右子树
105
. . .
A
110
120
B
...
new
右左--> 右右:
把绿色的110 整体对接到 105的右子树上,
105
. . .
A
110
B
120...
new
右左--> 右右:
把黄色的部分B-new 对接到合适的位置, 哪里合适呢? B 原来是105的右孩子, 所以B 肯定大于105,
105 原来是 110的左孩子, 所以 110>105>B, 也即 B肯定小于110, 而且110的左孩子原来是105, 切割之后110的左孩子肯定是空的, 所以B 的合适位置就是110的左孩子变换完毕
105
. . .
A
110
B
120...
new
右左--> 右右:
为什么这样变换后是把右左改变为右右不平衡了呢假设100的左子树高度是n
由于是不平衡, 100 的右子树高度肯定是 n+2
105
. . . A 110
B 120
...
new
右左--> 右右:
100.右. 左 高度是 n+2
100.右. 右 高度肯定是 n+1, 因为如果是
105
. . . A 110
B 120
...
new
右左--> 右右:
由于红色部分原来高度最大可能是N+2, 变换后提升了一个层次, 必然
105
. . . A 110
B 120
...
new
变换为 右右不平衡
至此已经把右左不平衡转换为了右右不平衡
左左不平衡: 是右右不平衡左右对称调换的解决方法
左右不平衡: 首先转变为左左不平衡 , 然后用左左解决方法