二叉排序树

一、二叉排序树的基本概念

1. 定义：
   • 二叉排序树（BST）是一种特殊的二叉树，它满足以下性质：
   ①若左子树非空，则左子树上所有节点的值均小于根节点的值。
   ② 若右子树非空，则右子树上所有节点的值均大于根节点的值。
   ③左子树和右子树也分别为二叉排序树。
2. 特点：
   ①中序遍历二叉排序树，可以得到一个递增的有序序列。
   ②没有键值相等的节点。

二、二叉排序树的基本操作

1. 查找操作：
   • 过程：从根节点开始，如果当前节点的值等于目标值，则查找成功；如果当前节点的值大于目标值，则继续遍历左子树；如果当前节点的值小于目标值，则继续遍历右子树。
   • 时间复杂度：最好情况下为O(log⁡n），最坏情况下为O(n)，取决于树的形态。
   算法代码：

1
2
3
4
5
6
7
8
9

BSTNode*BST_Search(BiTreeT,ElemTypekey)
{
	while(T!=NULL&&key!=T->data) //若树空或等于根结点值，则结束循环
	{
		if(key<T->data)T=T->lchild;//小于，则在左子树上查找
		elseT=T->rchild;//大于，则在右子树上查找}returnT
	}
	return T;
}

2. 插入操作：
   • 过程：首先查找要插入的位置（一定是叶子节点），然后创建新节点插入到该位置。
   • 时间复杂度：O(logn)，取决于树的形态。
   插入展示：
   
   算法代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int BST_Insert(BiTree&T,KeyTypek)
{
	if(T==NULL)
	{//原树为空，新插入的记录为根结点
		T=(BiTree)malloc(sizeof(BSTNode));
		T->data=k;
		T->lchilds=T->rchild=NULL;
		return1;//返回1,插入成功).
	}
	else if(k==sT->data)//树中存在相同关键字的结点，插入失败
		return0;
	else if(k<T->data)//插入到T的左子树
		return BST_Insert(T->lchildrk);
	else//插入到T的右子树
		return BST_Insert(T->rchild,k);
}

2. 删除操作：
   • 过程：
   • 找到要删除的节点，并确定其父节点。
   • 如果要删除的节点是叶子节点，直接删除。
   • 如果要删除的节点只有一个子节点，将其子节点代替要删除的节点。
   • 如果要删除的节点有两个子节点，找到其右子树中的最小节点或左子树中的最大节点，用该节点代替要删除的节点，并将其删除。
   • 时间复杂度：O(logn)，取决于树的形态。

删除展示：

三、二叉排序树的性质与应用

1. 性质：
   • 由于二叉排序树的性质，查找、插入和删除操作的时间复杂度通常为O(log⁡n)，但在最坏情况下（如树退化为链表）可能达到O(n)。
2. 应用：
   • 二叉排序树在数据库索引、符号表、字典等应用中非常常见，用于实现高效的查找、插入和删除操作。

四、二叉排序树的构造与调整

1.二叉排序树的构造：从一棵空树出发，依次输入元素，将他们插入二叉排序树中的合适位置。
设查找的关键字序列为{45,24,53,45,12,24}

算法代码：

1
2
3
4
5
6
7
8
9
10

void Creat_BST(BiTree&T,KeyTypestr[],int n)
{
	T=NULL;//初始时T为空树
	int i=0;
	while(i<n)
	{//依次将每个关键字插入到二叉排序树中
		BST_Insert(T,str[i]);
		i++;
	}
}

3. 调整：
   • 在实际应用中，为了避免二叉排序树退化为链表，可以采用平衡二叉树（如AVL树、红黑树）来保持树的平衡性。