二叉搜索树 & 平衡树 定义 二叉搜索树是一种二叉树的树形数据结构,其定义如下:
空树是二叉搜索树。
若二叉搜索树的左子树不为空,则其左子树上所有点的附加权值均小于其根节点的值。
若二叉搜索树的右子树不为空,则其右子树上所有点的附加权值均大于其根节点的值。
二叉搜索树的左右子树均为二叉搜索树。
二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有 个结点的二叉搜索树中,这些操作的最优时间复杂度为 ,最坏为 。随机构造这样一棵二叉搜索树的期望高度为 。
过程 在接下来的代码块中,我们约定 为结点个数, 为高度,val[x]
为结点 处存的数值,cnt[x]
为结点 存的值所出现的次数,lc[x]
和 rc[x]
分别为结点 的左子结点和右子结点,siz[x]
为结点的子树大小。
遍历二叉搜索树 由二叉搜索树的递归定义可得,二叉搜索树的中序遍历权值的序列为非降的序列。时间复杂度为 。
遍历一棵二叉搜索树的代码如下:
实现 void print ( int o ) {
// 遍历以 o 为根节点的二叉搜索树
if ( ! o ) return ; // 遇到空树,返回
print ( lc [ o ]); // 递归遍历左子树
for ( int i = 1 ; i <= cnt [ o ]; i ++ ) printf ( "%d \n " , val [ o ]); // 输出根节点信息
print ( rc [ o ]); // 递归遍历右子树
}
查找最小/最大值 由二叉搜索树的性质可得,二叉搜索树上的最小值为二叉搜索树左链的顶点,最大值为二叉搜索树右链的顶点。时间复杂度为 。
findmin 和 findmax 函数分别返回最小值和最大值所对应的结点编号 ,用 val[o]
可以获得相应的最小/最大值。
实现 int findmin ( int o ) {
if ( ! lc [ o ]) return o ;
return findmin ( lc [ o ]); // 一直向左儿子跳
}
int findmax ( int o ) {
if ( ! rc [ o ]) return o ;
return findmax ( rc [ o ]); // 一直向右儿子跳
}
插入一个元素 定义 insert(o,v)
为在以 为根节点的二叉搜索树中插入一个值为 的新节点。
分类讨论如下:
若 为空,直接返回一个值为 的新节点。
若 的权值等于 ,该节点的附加域该值出现的次数自增 。
若 的权值大于 ,在 的左子树中插入权值为 的节点。
若 的权值小于 ,在 的右子树中插入权值为 的节点。
时间复杂度为 。
实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 void insert ( int & o , int v ) {
if ( ! o ) {
val [ o = ++ n ] = v ;
cnt [ o ] = siz [ o ] = 1 ;
lc [ o ] = rc [ o ] = 0 ;
return ;
}
siz [ o ] ++ ;
if ( val [ o ] == v ) {
cnt [ o ] ++ ;
return ;
}
if ( val [ o ] > v ) insert ( lc [ o ], v );
if ( val [ o ] < v ) insert ( rc [ o ], v );
}
删除一个元素 定义 del(o,v)
为在以 为根节点的二叉搜索树中删除一个值为 的节点。
先在二叉搜索树中找到权值为 的节点,分类讨论如下:
若该节点的附加 大于 ,只需要减少 。
若该节点的附加 为 :
若 为叶子节点,直接删除该节点即可。
若 为链节点,即只有一个儿子的节点,返回这个儿子。
若 有两个非空子节点,一般是用它左子树的最大值或右子树的最小值代替它,然后将它删除。
时间复杂度 。
实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 int deletemin ( int & o ) {
if ( ! lc [ o ]) {
int u = o ;
o = rc [ o ];
return u ;
} else {
int u = deletemin ( lc [ o ]);
siz [ o ] -= cnt [ u ];
return u ;
}
}
void del ( int & o , int v ) {
// 注意 o 有可能会被修改
siz [ o ] -- ;
if ( val [ o ] == v ) {
if ( cnt [ o ] > 1 ) {
cnt [ o ] -- ;
return ;
}
if ( lc [ o ] && rc [ o ]) {
int t = deletemin ( rc [ o ]);
lc [ t ] = lc [ o ];
rc [ t ] = rc [ o ];
siz [ t ] = siz [ o ];
o = t ;
}
// 这里以找右子树的最小值为例
else
o = lc [ o ] + rc [ o ];
return ;
}
if ( val [ o ] > v ) del ( lc [ o ], v );
if ( val [ o ] < v ) del ( rc [ o ], v );
}
求元素的排名 排名定义为将数组元素排序后第一个相同元素之前的数的个数加一。
查找一个元素的排名,首先从根节点跳到这个元素,若向右跳,答案加上左儿子节点个数加当前节点重复的数个数,最后答案加上终点的左儿子子树大小加一。
时间复杂度 。
实现 int queryrnk ( int o , int v ) {
if ( val [ o ] == v ) return siz [ lc [ o ]] + 1 ;
if ( val [ o ] > v ) return queryrnk ( lc [ o ], v );
if ( val [ o ] < v ) return queryrnk ( rc [ o ], v ) + siz [ lc [ o ]] + cnt [ o ];
}
查找排名为 k 的元素 在一棵子树中,根节点的排名取决于其左子树的大小。
若其左子树的大小大于等于 ,则该元素在左子树中;
若其左子树的大小在区间 ( 为当前结点的值的出现次数)中,则该元素为子树的根节点;
若其左子树的大小小于 ,则该元素在右子树中。
时间复杂度 。
实现 int querykth ( int o , int k ) {
if ( siz [ lc [ o ]] >= k ) return querykth ( lc [ o ], k );
if ( siz [ lc [ o ]] < k - cnt [ o ]) return querykth ( rc [ o ], k - siz [ lc [ o ]] - cnt [ o ]);
return val [ o ];
// 如要找排名为 k 的元素所对应的结点,直接 return o 即可
}
平衡树简介 使用二叉搜索树的目的之一是缩短插入与查找时间,一棵合理的二叉搜索树插入与查找时间可以缩短到 。
对于一般的二叉搜索树,有可能退化为链表。想象一棵每个结点只有右孩子的二叉搜索树,那么它的性质就和链表一样,插入与查找时间都是 ,可以说是极大的时间浪费,所以研究平衡二叉搜索树是非常有必要的。
关于查找效率分析,如果树的高度为 ,则在最坏的情况,查找一个关键字需要对比 次,查找时间复杂度(也为平均查找长度 ASL,Average Search Length)不超过 。
二叉搜索树的「平衡」概念是指:每一个结点的左子树和右子树高度差最多为 。
可以对不满足平衡条件的二叉搜索树进行调整,使不平衡的二叉搜索树变得平衡。
调整要保证的标准还有二叉搜索树先天自带的条件:二叉搜索树,按照中序遍历,得到从小到大的结点值序列。对于任意一个结点,左子树各结点的最大值,小于该结点的值;该结点的值,小于右子树各结点的最小值。只有保证这一点才能称为一个二叉搜索树。
对于拥有同样元素值集合的二叉搜索树,平衡状态可能是不唯一的。也就是说,可能两棵不同的二叉搜索树,含有的元素值集合相同,并且都是平衡的。
过程 保证中序遍历序列不变的平衡调整,基本操作为 右旋(rotate right 或者 zig) 和 左旋(rotate left 或者 zag) 。这两种操作均不改变中序遍历序列。
在这里先介绍右旋,右旋也称为「右单旋转」或「LL 平衡旋转」。对于结点 的右旋操作是指:将 的左孩子 向右上旋转,代替 成为根节点,将 结点向右下旋转成为 的右子树的根结点, 的原来的右子树变为 的左子树。
右旋操作只改变了三组结点关联,相当于对三组边进行循环置换一下,因此需要暂存一个结点再进行轮换更新。
对于右旋操作一般的更新顺序是:暂存 结点,先让 的左孩子指向 的右子树 ,再让 的右孩子指针指向 ( 被它的父结点指向),最后让 的父结点指向暂存的 。整个操作只要找到 的父节点孩子即可完成。
完全同理,有对应的左旋操作,也称为「左单旋转」或「RR 平衡旋转」。左旋操作与右旋操作互为镜像。
一段可行的代码为:
实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 int zig ( int now ) { // 以now为中心右旋
int lchild = nodes [ now ]. lchild ; // 暂存A的左孩子B节点
nodes [ now ]. lchild = nodes [ lchild ]. rchild ; // 将A的左孩子指向B的右子树BR
nodes [ lchild ]. rchild = now ; // 将B的右孩子指针指向A
update ( nodes [ lchild ]. rchild ); // 更新旋转后A与B两个节点的信息
update ( lchild );
return lchild ; // 让A的父节点指向最初暂存的B
}
int zag ( int now ) { // 以now为中心左旋
int rchild = nodes [ now ]. rchild ;
nodes [ now ]. rchild = nodes [ rchild ]. lchild ;
nodes [ rchild ]. lchild = now ;
update ( nodes [ rchild ]. lchild );
update ( rchild );
return rchild ;
}
对于这段示例代码,只有调用者知道结点 的父结点是什么。对于这种情形,代码的返回值为新的子树根结点的下标,令调用者将左边为 的父节点赋值为指向新的子树根结点的下标即可。
对于拥有同样元素值集合的全体合法的二叉搜索树,可以证明,在任意两棵树之间均可通过若干右旋和左旋操作,完成从一棵树到另一棵树的变换。因此,借助右旋和左旋操作,可以将任意一棵合法的二叉搜索树调整至平衡状态。
本页面最近更新:2023/5/17 16:20:52 ,更新历史 发现错误?想一起完善? 在 GitHub 上编辑此页! 本页面贡献者:2323122 , aofall , AtomAlpaca , Bocity , CoelacanthusHex , countercurrent-time , Early0v0 , Enter-tainer , fearlessxjdx , Great-designer , H-J-Granger , hsfzLZH1 , iamtwz , Ir1d , ksyx , Marcythm , NachtgeistW , ouuan , Persdre , shuzhouliu , StudyingFather , SukkaW , Tiphereth-A , wsyhb , Yesphet 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用