数据结构-树-二叉搜索树-03

数据结构-树-二叉搜索树-03

查找问题

  • 静态查找(二分查找)和动态查找
  • 针对动态查找,数据如何组织

什么是二叉搜索树

一棵二叉树,可以为空;如果不为空,满足以下性质(左小右大)

  1. 非空左子树的所有键值小于其根结点的键值

  2. 非空右子树的所有键值大于其根结点的键值。

  3. 左、右子树都是二叉搜索树

查找操作

Positon Find(ElmentType X,BinTree BST)
{
	if(!BST){
		return NULL;//空的话查找失败
	}
	if(X > BST->Data){
		return Find(X,BST->Right);//大于到右边找
	}
	Else if(X < BST->Data){
		return Find(X,BST->Left);
	}
	else // x == BST->Data
        return BST;
}

由于递归的执行效率低,我们可以循环来做尾递归函数

Position IterFind(ElementType X,BinTree BST)
{
	while(BST){
		if(X > BST->Data){
			BST = BST->Right;//比他大,则指针向右走
		}
		else if(X < BST->Data){
			BST = BST->Left;
		}
		else{
			return BST;
		}
	}
}

查找的效率决定于数的高度,二叉搜索树的时间复杂度为log2N

二叉搜索树的时间复杂度

由于二分查找每次查询都是从数组中间切开查询,所以每次查询,剩余的查询数为上一次的一半,从下表可以清晰的看出查询次数与剩余元素数量对应关系

第几次查询 剩余待查询元素数量
1 N/2
2 N/(2^2)
3 N/(2^3)
……
K N/(2^K)

从上表可以看出N/(2K)肯定是大于等于1,也就是N/(2K)>=1,我们计算时间复杂度是按照最坏的情况进行计算,也就是是查到剩余最后一个数才查到我们想要的数据,也就是
$$
N/(2^K)=1
=>N=2^K
=>K=log2N
$$

所以二分查找的时间复杂度为O(log2N)

查找最大值和最小值

  • 最大值在树的最右分支节点上
  • 最小值在数的最左分支节点上
Position FindMin(BinTree BST){
	if(!BST){
		return NULL;
	}
	else if(!BST->Left){
		return BST;
	}
	else{
		return FindMin(BST->Left)//沿着左分支点不停查找
	}
}	
Position FindMax(BinTree BST){
	if(BST){
		while(BST - > Right){
			BST = BST->Right;//利用循环实现
		}
		return BST;
	}
}

二叉搜索树的插入和删除

  • 插入
BinTree Insert( ElementType X, BinTree BST )
{
 if( !BST ){
 /*若原树为空,生成并返回一个结点的二叉搜索树*/
 	BST = malloc(sizeof(struct TreeNode));
 	BST->Data = X;
 	BST->Left = BST->Right = NULL;
 }
 else /*开始找要插入元素的位置*/
 	if( X < BST->Data )
 		BST->Left = Insert( X, BST->Left);
 		/*递归插入左子树*/
 	else if( X > BST->Data )
 		BST->Right = Insert( X, BST->Right);
 				/*递归插入右子树*/
 	/* else X已经存在,什么都不做 */
 return BST;
}

  • 删除
    • 要删除的是叶结点:直接删除,并再修改其父结点指针---置为NULL
    • 要删除的结点只有一个孩子结点: 将其父结点的指针指向要删除结点的孩子结点
    • 要删除的结点有左、右两棵子树:用另一结点替代被删除结点:右子树的最小元素 或者 左子树的最大元素

数据结构-树-二叉搜索树-03

BinTree Delete( ElementType X, BinTree BST )
{ 
    Position Tmp;
 	if( !BST ) printf("要删除的元素未找到");
 	else if( X < BST->Data )
 		BST->Left = Delete( X, BST->Left); /* 左子树递归删除 */
 	else if( X > BST->Data )
 		BST->Right = Delete( X, BST->Right); /* 右子树递归删除 */
 	else /*找到要删除的结点 */
 		if( BST->Left && BST->Right ) { /*被删除结点有左右两个子结点 */
 			Tmp = FindMin( BST->Right );
 			/*在右子树中找最小的元素填充删除结点*/
 			BST->Data = Tmp->Data;//将右边子树的最小值填充到要删除的节点上
 			BST->Right = Delete( BST->Data, BST->Right);
 					/*在删除结点的右子树中删除最小元素*/
 		} else { /*被删除结点有一个或无子结点*/
			Tmp = BST;
			if( !BST->Left ) /* 有右孩子或无子结点*/
 				BST = BST->Right;
	 		else if( !BST->Right ) /*有左孩子或无子结点*/
 				BST = BST->Left;
 			free( Tmp );
 		}
 return BST;
}

平衡二叉树

搜索树结点的不同插入次序,将导致不同的深度和平均查找长度ASL。

平衡因子(Balance Factor,简称BF): BF(T) = hL-hR,

其中hL和hR分别为T的左、右子树的高度。

平衡二叉树:AVL树,指的是空树或者是任一节点左右子树高度差的绝对值不超过1,即|BF(T)|<= 1

数据结构-树-二叉搜索树-03

示例:上面的例子中,第一幅图3,5子树不符合高度差为1,第三幅图中,7这个节点左边多两层,同样不符合定义。

平衡二叉树的高度

数据结构-树-二叉搜索树-03

通过数学推断,给定节点树为n的AVL数的最大高度为O(log2N)!

平衡二叉树的调整

当插入节点的时候,会把原先平衡的二叉树变得不平衡,我们如何进行调整呢?

  • RR旋转:原来平衡,插右子树的右边入结点使得平衡破坏,将整个树向右旋转。

  • LL旋转:“麻烦结点”在发现者左子树的左边, 因而叫 LL 插入,需要LL 旋转(左单旋)

  • LR旋转:麻烦节点在左子树的右边,也就是LR插入,需要LR旋转。(关键把插入节点前面的前三个节点调平衡)

  • RL旋转:麻烦节点在右子树的左边,也就是RL插入,需要RL旋转。(关键把插入节点前面的前三个节点调平衡)

是否为同一颗二叉搜索树

  • 给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。

    • 例如,按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树, 都得到一样的结果。
  • 问题:对于输入的各种插入序列,你需要判断它们是否能 生成一样的二叉搜索树。

  • 求解思路

    • 分别建两棵搜索树的判别方法
    • 不建树的判别方法:利用递归,将子树分类,查看是否一样
    • 建一棵树,再判别其他序列是否与这个树一致
      • 搜索树表示
      • 建搜索树T
      • 判别一序列是否与搜索树T一致
//搜索树的定义
typedef struct TreeNode *Tree;
struct TreeNode {
		int v;
		Tree Left, Right;
		int flag;//节点有没有访问过的标记
};
//程序主体
int main()
{ 		
    int N, L, i;//N代表元素个数,L是代表有多少个序列需要比较
 	Tree T;
 	scanf("%d", &N);
 	while (N) {//当N不为0时
		scanf("%d", &L);
		T = MakeTree(N);//读取数据建搜索树T
		for (i=0; i<L; i++) {//一共要判断多少个序列,循环判定
 			if (Judge(T, N))//判别序列是否与构成一样的搜索树
                printf("Yes\n");
 			else 
                printf("No\n");
 			ResetT(T); /*清除T中的标记flag*/
		}
		FreeTree(T);//一组数据处理完了,要处理下一组数据,将之前数据清除
		scanf("%d", &N);
 	}
 return 0;
}
//如何建搜索树
Tree MakeTree(int N)
{
    Tree T;
    int i,V;
    
    scanf("%d",&V);//V代表第一个数
    T = NewNode(V);
    for(i = 1;i<N;i++){//读入后面的N-1个数
        scanf("%d",&V);
        T = insert(T,V);//二叉搜索树的查找
    }
}

Tree NewNode(int V)
{
	Tree T = malloc(sizeof(struct TreeNode));
    T->v = V;
    T->Left = NULL;
    T->Right = NULL;
   	T->flag = 0;//flag = 0表示没有访问
    return T;
}
Tree insert()
{
    if(!T) = NewNode(V);//先判别T空不空,空则用NewNode产生新节点赋给T
    else{
        if(V>T-v)
            T->Right = insert(T->Right,V);//递归调用
        else
            T->Left = insert(T->Left,V);
    }
    return T;
}

如何判别搜索树和序列是否一致

查找这个序列中每一个整数在这个树中的位置,如果在查找的过程中发现某个位置以前没碰到过,那就说明二者不一致,如果所有树都碰到过,那么就一致,比如在下图中,我们去查找2,发现第一幅图中查找2的路径为3-1-2,而在树中只有3-2,那么就不一致

数据结构-树-二叉搜索树-03

int check ( Tree T, int V )//在T里去搜索序列中的每一个整数,查找过程中判断序列和树是否一致
{
	if ( T->flag ) {
        //flag为1时候,flag被访问过了
        //flag ==0 代表未访问, ==1代表访问过
		if ( V<T->v ) 
            return check(T->Left, V);//数值小,则去左子树找
		else if ( V>T->v ) 
            return check(T->Right, V);
		else //如果相等,因为当前节点已经被访问过了,则这个数序列中重复出现了两次
            return 0;//访问两次,不一致
	}
	else {//flag为0,没有被访问过
		if ( V==T->v ) {//判断当前节点是否和查找值一样
			T->flag = 1;//如果一样,则已经访问flag设置为1
			return 1;//节点一样,而且没被访问过,证明一致
		}
		else return 0;//flag为0,碰到了一个以前没见过的节点,路径不一致
	}
}
int Judge( Tree T, int N )//判别每一个整数是不是一致的
{
	int i, V, flag = 0;
 		/* flag: 0代表目前还一致,1代表已经不一致*/
	scanf("%d", &V);
	if ( V!=T->v ) //v是第一个数,代表树根
        flag = 1;//如果树根不一样,那么不一致
	else 
        T->flag = 1;
	for (i=1; i<N; i++) {//顺序读入后面N个整数
		scanf("%d", &V);
		if ( (!flag) && (!check(T, V)) ) 
        //flag的目的是当我发现有矛盾了,还让程序继续做
        //flag为0,check为0表示刚刚发现了矛盾
		{
            flag = 1;
		}
	if (flag) 
        return 0;//如果有不同,返回1
	else 
        return 1;
}
void ResetT ( Tree T ) /* 清除T中各结点的flag标记 */
{
	if (T->Left) 
        ResetT(T->Left);
	if (T->Right) 
        ResetT(T->Right);
	T->flag = 0;//递归调用,全部重置为0
}
void FreeTree ( Tree T ) /* 释放T的空间 */
{
	if (T->Left) 
        FreeTree(T->Left);
	if (T->Right) 
        FreeTree(T->Right);
	free(T);//全部释放内存空间
}
上一篇:[转载]如何申请淘宝app_key、app_secret、SessionKey?


下一篇:SQL数据类型和C#数据类型间的转换