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

▎前言

小编虽然早已会了二叉排序树，但是仍不明白静态二叉排序树和二叉排序树有哪个关系。

结合平衡二叉排序树（例如：红黑树）食用本篇博客，效果最佳哦～

传送门（同时也内含二叉排序树的相关知识）

▎静态二叉排序树

『引入』

这个东西要从线段树说起，别问我为什么扯这么远。

戳这里快速上手线段树。

不得不说，线段树是个好东西，每次都会把一个区间劈成左右两半，运用了分治的观念。

但是线段树更多的是拿来处理区间类的难题二叉排序树 建立，在遭遇数据点统计问题的之后，也可算起来，不过多保留了一下一些冗余的东西。

比如说：线段树总是定义过多的l，r，mid指针来指向区间，这就是冗余信息;

再比如说：线段树的结点是用来存储区间的，而在处理点的难题时，是不需要的，这就是冗余信息。

还有：在处理点时，线段树的区间一分为二二叉排序树 建立，是借助一个分割点的，只要保留这个分割点就可以了。

像这种的冗余信息不止这些，但是即使我们换成二叉排序树就不同了。

『定义』

个人觉得二叉排序树和静态二叉排序树在定义上没有区别。

『特点』

用示例来说吧：

比如说现在有这种一组数据：3,6,9,2,5,4,1。

先明确一下位置关系：

假设当前结点为i，那么左子树编号为i×2,右子树编号为i×2+1,所以我们用数组进行存储的之后就是按照这个规律来存储的。

先创建一个映射X={1,2,3,4,5,6,9}（说白了就是排序一遍）。

接着用这个映射根据二叉排序树的性质开始填入：

发现规律了吗？1,2,3,4,5,6,9恰好是这棵树的中序遍历顺序。

也就是说静态二叉排序树插入点是靠中序遍历的，但是二叉排序树不一样，插入模式跟搜索时更像。

▎静态二叉排序树的查找

这个很简单吧，直接上代码：

1 void build(int i)
2 {
3     if(i*2<=n) build(i*2);
4     tree[i]=x[++cnt];
5     if(i*2+1<=n) build(i*2+1);
6 }

▎静态二叉排序树的特点

容易看出，静态二叉排序树及其相近满二叉树，有时就是！

所以静态二叉排序树天生就是平衡树。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-144343-1.html