【算法•日更•第四十四期】虚二叉树

水深无声 2023-06-03 02:52 20阅读 0赞

▎前言

小编菜归菜，但是好歹也写过几篇关于树的博客：[线段树][Link 1]、[划分树][Link 2]、[红黑树][Link 3]。

如果你已经会了这些树，那么你一定会认为树很麻烦，很烧脑。

其中的红黑树是一种二叉排序树实现自平衡的树，但是最烦人，线段树和划分树都很好写，而红黑树不仅要建树、查找，还要再实现自平衡。

但是虚二叉树和红黑树功能一样，只不过更大的优点在于计数，却免去了建树和实现自平衡的过程。

▎虚二叉树

☞『定义』

这个东西在百度上找不着定义。

通常的静态二叉排序树，需要先构造一棵空树，而虚二叉树巧妙的结合了二分法，省略掉了这个过程。

由于不直接去构造二叉树，所以便失去了二叉树的外显形式，因此我们称之为：虚二叉树。

说白了就是免去建树的静态二叉排序树，所以说是“虚”二叉树。

☞『算法核心』

在我们对一个有序的数列进行二分查找时，实际上就相当于对一棵二叉树进行查找。

例如下面就是一个二分查找的示例程序：

1 int search(int x)
     2 {
     3     int l=1,r=n;
     4     while(l<=r)
     5     {
     6         int mid=(l+r)>>1;
     7         if(v[mid]==x) return mid;
     8         if(v[mid]>x) r=mid-1;
     9         else l=mid+1;
    10     }    
    11 }

其中我们不难发现mid始终就是\[l,r\]区间的中点，类似于二叉树中的根。

而左边\[l,mid-1\]则形成了其左子树形态。

右边\[mid+1,r\]则形成了其右子树的形态。

这棵二叉树就是虚二叉树。

相信用过树的大家应该都知道使用数组完全是靠节点编号关系来判断的，所以根不一定是最中间的，但是虚二叉树的根是在中间的。

虚二叉树虽然不是近似满二叉树，也没有静态二叉排序树那样完美的结构，但是却是天然的平衡二叉树，由二分查找的过程知道最多查找log n次即可，因此虚二叉树和平衡二叉树的时间复杂度相差无几，却大大降低了代码复杂度。

☞『不同』

虚二叉树不就是二分查找吗？相信你早已开始吐槽了。

其实虚二叉树与二分查找不一样，最大的不同正是它的优点。

在实现静态二叉排序树时，我们就会把所有的需要修改的量都保留在根节点上，虚二叉树也可以这样做，每棵子树的根节点实际上就是mid，那么我们就可以在mid上保留信息了。

其实这一个不同和虚二叉树的用途有关，虚二叉树可以利用这一点统计个数。

☞『优点』

我们只要想象这棵二叉树长什么样，理解就不困难了。

这样的的虚实现省去了构造，实现上就得以进一步简化。

转载于:https://www.cnblogs.com/TFLS-gzr/p/11363785.html

[Link 1]: https://www.cnblogs.com/TFLS-gzr/p/11237190.html
[Link 2]: https://www.cnblogs.com/TFLS-gzr/p/10331352.html
[Link 3]: https://www.cnblogs.com/TFLS-gzr/p/10051016.html

发表评论取消回复

表情：

评论列表（有 0 条评论，20人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法•日更•第五十四期】知识扫盲：什么是operator？

▎前言　　这个东西和迭代器长的很像，但是比迭代器常见的多。　　今天就来浅谈operator。 ▎定义 > 　　operator是C\、C++和pascal的关键字，

你的名字/ 2023年06月03日 02:52/ 0 赞/ 45 阅读

相关【算法•日更•第四十九期】双系统

　　双系统是实现使用两个系统的第二个方式，众所周知，虚拟机是个好东西，但是有众多不便的地方：　　![1551435-20190818220507151-1405964119

爱被打了一巴掌/ 2023年06月03日 02:52/ 0 赞/ 74 阅读

相关【算法•日更•第四十八期】二分图（匈牙利算法）

▎前言　　小编最近看来hza大佬的博客，也来写一篇匈牙利算法的博客。　　小编决定写的不一样点。 ▎前置知识　　二分图的基础知识。　　[传送门][Link 1]

灰太狼/ 2023年06月03日 02:52/ 0 赞/ 90 阅读

相关【算法•日更•第四十七期】Mac与windows系统的差别

　　小编最近装了个Mac系统，因为小编已经有笔记本可以用linux了，所以就决定在台式机上装个双系统，结果一不小心把Mac装在C盘上了，哎，说多了都是泪啊。 ![155143

墨蓝/ 2023年06月03日 02:52/ 0 赞/ 32 阅读

相关【算法•日更•第四十六期】二分图（基础）

▎前言　　小编昨天写了关于静态二叉排序树的建立，但是小编今天果断的不写静态二叉排序树的使用了，因为写了就感觉在专门水博客。　　前段时间老师问我会不会二分图，小编才知道有

忘是亡心i/ 2023年06月03日 02:52/ 0 赞/ 10 阅读

相关【算法•日更•第四十五期】静态二叉排序树（建立）

▎前言　　小编虽然已经会了二叉排序树，但是却不明白静态二叉排序树和二叉排序树有什么关系。　　结合平衡二叉排序树（例如：红黑树）食用本篇博客，效果更佳哦～　　[传送门

绝地灬酷狼/ 2023年06月03日 02:52/ 0 赞/ 2 阅读

相关【算法•日更•第四十四期】虚二叉树

▎前言　　小编菜归菜，但是好歹也写过几篇关于树的博客：[线段树][Link 1]、[划分树][Link 2]、[红黑树][Link 3]。　　如果你已经会了这些树，那么

水深无声/ 2023年06月03日 02:52/ 0 赞/ 21 阅读

相关【算法•日更•第四十三期】QQ for linux

　　废话不多说，直接看一张图：　　![1551435-20190814185233383-371284311.png][] 　　没错，这是QQ，但是这有什么稀奇的？但是在

浅浅的花香味﹌/ 2023年06月03日 02:52/ 0 赞/ 52 阅读

相关【算法•日更•第三十四期】最大流算法

▎写在前面　　在之前，我们已经清楚了网络流与最大流是什么，以及增广的操作。　　如果你还不会请点击学习。　　[传送门][Link 1] ▎基本思路　　先放上一张

不念不忘少年蓝@/ 2023年06月03日 02:51/ 0 赞/ 25 阅读

相关【算法•日更•第四十三期】QQ for linux

　　废话不多说，直接看一张图：　　![1551435-20190814185233383-371284311.png][] 　　没错，这是QQ，但是这有什么稀奇的？但是在

柔情只为你懂/ 2021年10月26日 15:58/ 0 赞/ 263 阅读