二叉查找树二叉查找树
什么是二叉查找树什么是二叉查找树
所谓二叉查找树,就是严格任一左子树小于根,右子树大于根的二叉树,平均情况在O(logn)O(log n)O(logn)内查找数据元
素。在大规模数据的搜索中,显然最简易的方法是利用快速排序或者归并排序对数据进行排序,然后根据下标来查询具体位置
的具体数值,期望值为O(nlogn)O(nlog n)O(nlogn),而利用二叉查找树,则可在输入时对数据进行处理,期望
O(logn)O(logn)O(logn)的时间查找位置。
插入插入
对于二叉查找树的插入,只需从根结点开始,不断比较当前结点与该元素的大小关系,较小向左子树递归,较大向右子树递
归,直至找到插入位置。特别地,当结点数值大小与该元素相同时,只需修改该结点的cntcntcnt值。
删除删除
对于删除,同样先查找数据所在位置,修改该结点cntcntcnt值。特别地,当cnt==0cnt == 0cnt==0时,表示二叉查找树中已无
该数值。
查找查找
之所以有二叉查找树这种较普通二叉树更高级的数据结构,重点就是为了提高查找的效率。
1.查找前驱和后继查找前驱和后继
对于前驱和后继,其实方法等同于插入,只不过对于前驱而言,要一直查找到没有右子树为止,以确保前驱最大;同样,查找
后继时要直到没有左子树为止,以保证后继最小。
2.按排名找值按排名找值
此时结构体中的size值将发挥作用,它用于记录以该结点为根包括该结点在内的树的大小。此时根据排名,可以通过不断比较
结点的size值,找到所要确定的值。
3.按值找排名按值找排名
对于给定的数值,要确定其的位置,同样,首先通过不断递归找到该元素,然后不断将结点值之间的size值做差,最后得到元
素的具体位置。
ps:ps:ps:对于二叉查找树而言,其查找效率已经大幅提高,然后对于输入为递增或递减的数据而言,其会退化成O(n)O(n)O(n)
的单链,关于这种情况的改进,则需要一种更高级的数据结构——二叉平衡树。
#include
using namespace std;
const int maxn = 9e2 + 16;
const int INF = 0x7fffffff;
int pos;
typedef struct BinarySearchTree
{
int val; //表示权值
int rank; //表示排名
int size; //表示当前结点子树大小(包括该结点)
int cnt; //表示当前结点的数量
int ls, rs; //表示左右子树
}bst;
bst tree[maxn];
void add(int cur, int v) //实现结点的插入
{
tree[cur].size++;
if (tree[cur].val == v)
{
tree[cur].cnt++;
return;
}
if (tree[cur].val > v)
{
if (tree[cur].ls != 0)
{
add(tree[cur].ls, v);
}
else
{
pos++;
tree[pos].val = v;
tree[pos].size = 1;
tree[pos].cnt = 1;
- 1
- 2
前往页