当前位置:首页 > 天道酬勤 > 正文内容

数据结构中平衡因子怎么求(数据结构二叉排序树)

张世龙2021年12月21日 19:26天道酬勤290

资料来源:艰苦的码农

作者:很帅

红树是很难的数据结构吧。 很少考察插入、删除等具体的操作步骤。 如果遇到要求你手写红树的面试官,就直接告辞吧。 所以,多考察你对红黑树的了解程度,最多考察的是,有人问为什么两个探索树/平衡树还需要红黑树? 今天,你一分钟就能知道怎么回答这个问题。

一、叉叉找树的缺点

二叉搜索树,我想大家都接触过,二叉搜索树的特征是:安静的老鼠节点值比父亲的节点小,右边的孩子树节点值比父亲的节点大。 图

基于这种二叉搜索树的特征,在搜索某个节点时,可以采用类似二分搜索的思路,快速搜索某个节点。 n个节点的二叉树在正常情况下搜索的时间复杂度为O(logn )。

之所以说正常,是因为二叉搜索树有可能出现极端的情况。 例如

这种情况下也满足二叉树的条件,但是此时的二叉树简并为链表,这样的二叉树搜索树的搜索时间的复杂性突然变为o(n ),为了解决这种状况,需要进行平衡2、平衡二叉树

平衡二叉树是为了解决二叉搜索树退化成为链表而诞生的,平衡树具有以下特征

具有一、二叉搜索树的所有特性。

2、各节点安静的老鼠和右子的高度差最多等于1。

例如,图1是平衡树,但图2不是。 (节点右侧的目标是此节点的高度。

因为在图2中,节点9的左边孩子的高度为2,右边孩子的高度为0。 他们之间的差距超过了1。

平衡树基于这个特点,保证了许多节点不会偏向一侧。 此处不介绍平衡树的构建、插入、删除、向左旋转、向右旋转等操作。 具体可以读我以前写的文章。 【漫画】接下来,如果面试官问了AVL树,请把这篇文章扔给他。

于是,通过平衡树,解决了叉叉找树的缺点。 在具有n个节点的平衡树中,最坏搜索时间的复杂度也为o(logn )。

3、为什么即使有平衡木也需要红黑树?

平衡树可以解决二叉树退化为接近链表的形状的缺点,将搜索时间控制在o(logn ),但不是最佳的。 因为平衡树要求每个节点的安静老鼠和右子的高度差最大为1,所以这个要求非常严格,每次插入/删除节点,平衡树的第二个规则几乎都会崩溃。 而且,需要进行左转和右转的调整,使之再次一致

很明显,在经常插入和删除的场景中,需要经常调整平衡树,这大大降低了平衡树的性能。 为了解决这个问题,有一棵红黑树。 红色的树有以下特征。

具有1、二叉搜索树的特点。

2、根节点为黑色

3、各叶节点是黑色的空节点(NIL ),也就是说叶节点中不保存数据。

4、任何相邻的节点都不能同时变成红色。 也就是说,红色节点由黑色节点分隔。

5、各节点从其节点到可到达的叶节点是所有路径,包含相同数量的黑节点。

例如,下面的照片(请注意,照片中的黑色天空叶节点未被描绘) (照片来自极客时间) )。

根据这种红色黑色树的特征,即使在最坏的情况下,也可以发现o(logn )的时间复杂度即节点。 关于为什么能保证时间的复杂性为o(logn ),这里不详细说明,也许在后面的文章中说明。

但是,与平衡树不同,红黑树进行插入、删除等操作,不像平衡树那样频繁破坏红黑树的规则,所以不需要频繁调整。 因此,我们经常使用红黑树。

但是,如果说只有寻找才有效率的话,平衡树比红黑树要快。

所以,也可以说红黑的树是不太严格的平衡木。 也可以说是折中方案。

如果我在上面讲过,你都明白,能在面试中讲,我想就够了。 我是这样回答的。

4、总结

所以,最后的答案是,平衡树是为了解决二叉树退化为链表的情况,红黑树是为了解决平衡树需要通过插入、删除等操作频繁调整的情况。

但是,红黑树还有很多其他知识点。 例如,红黑树有哪些应用场景? 集合容器使用的是HashMap、TreeMap等,内部结构使用的是红黑树。 有时构建一棵节点数为n的红、黑树,时间的复杂性有多高? 红黑树和散列表应该在不同的场合选择吗? 红色、黑色的树有什么性质? 红黑树的各种操作的时间复杂度是多少?

扫描二维码推送至手机访问。

版权声明:本文由花开半夏のブログ发布,如需转载请注明出处。

本文链接:https://www.zhangshilong.cn/work/26530.html

分享给朋友:

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。