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

2024-01-12 12:06:52

数据结构-树-二叉搜索树-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#数据类型间的转换