为什么需要平衡二叉树?

时间:2021-05-29 17:30:57

前言:最近看《计算机科学的基础》以及老大的代码,很需要树结构的相关基本知识内容,在看老大的源码关于BT和RBT的时候,将平衡树和二叉排序树,关联到一起了。简单说明记录一下!

一、如何调整失衡树为平衡树

呃,如何调整的内容,很多人都总结过了,我就借花献佛,直接引用啦(好吧,我是不会承认我不会,还很懒滴)

动画演示平衡二叉树旋转

二、为什么要调整

我最开始想到这个问题的时候,是在看老大代码的时候,我先看的是BT代码,后来我在看RBT的时候,看到了旋转平衡处理, 然后我就很懵逼,不明白为什么要转,因为不转的话,也是符合排序树的标准的。   还有一个很蠢萌的问题是:我一直以为BT是二叉,其实他奶奶个腿儿,是多路搜索,我呸,暴露智商了!

话说回来,为什么要调整:平衡二叉树

简单说来,平衡二叉树,一定是二叉排序树,之所以将排序树,调整为平衡状态,是为了在二叉排序树近似为链的情况下,增强其查找性能,降低时间复杂度。

三、写本篇博客的动机

其实,从上述内容来看,我整篇文章几乎没有自己的内容去表达技术问题,那我为什么写这篇博客呢?

1,我将我学过的内容,联系起来了。  因为老大给我推荐的书《计算机科学的基础》最近刚好看到树结构和表结构模型,我一直在想二叉排序树的内容,包括树的存储方式。 今天看BT和RBT的时候,突然就觉得,RBT的性能肯定综合会比BT高,为什么呢,因为二叉排序树的特性会比多路搜索要简单处理,你想一下嘛:二叉排序树,不是在这边,就是在那边(二选一),而多路搜索,我也不知道是几选几啊,还有分裂,好吧,这真不是我智商低的托词。

2,为什么需要排序? 我记得我一个老师说过:排序是为了更好的存储和更快速地操作。然后,基于这一点,结合到我看书的表结构模型,我就想到了一个问题(或者说是发现了一个问题):主键的设置方式,之前我有做过系统,主键都是采用的自增式;但现在的系统,都是随机生成的唯一标识码。  我就在想,如果说排序是为了提升操作的效率,那为什么弃掉了主键自增的方式呢? 如果没有主键自增,那么在索引里面的体现会是什么样?  这些问题,我都查了一遍。  但主要是想说:知识是可以联系起来的,当把知识联系起来的时候,很有成就感!

四、个人总结

今天,总的来说,是很完美的一天。 因为我之前看老大的代码,有些地方都不是很明白,然后还要厚着脸皮问。虽然面上没红,但心里一直鄙视自己的智商。 但是,我坚持下来了,今天把全部的代码看完了,我说了说我的理解,貌似还是没有全对,但是自己找到感觉了。

其实,我还在想,到底什么场景下,用树结构的孩子兄弟表示法?因为现在大多数都是双亲表示法。 我今天在看BT的相关内容时,灵机一现,我靠,多路搜索,肯定要存兄弟节点呀。  呃,只是自己瞎想想啊!