动态查找表(二叉排序树)（第九章 P227 算法9.5-9.8）_eq(p->data==key)

二叉排序树

 

定义

二叉排序树(Binary Sort Tree)，又称二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树：

1. 若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
2. 若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
3. 它的左、右子树分别为二叉排序树。

 

二叉排序树的查找

 

二叉排序树的查找可以用递归来实现；先将要查找的关键字和根节点进行比较; 若和根节点值相同，则返回根节点值；若比根节点小，就递归查找左子树，若比根节点大，则递归查找右子树。

 

插入操作

 

先调用查找操作将要插入的关键字进行比较，如果在原有的二叉排序树中没有要插入的关键字，则将关键字与查找的结点p（在查找操作中返回的结点）的值进行比较。

若p为空，则插入关键字赋值给该节点

若小于结点p的值，则插入关键字作为结点p的左子树；

若大于结点p的值，则插入关键字作为结点p的右子树；

 

 

删除操作

 

二叉排序树的删除操作相对复杂，因为不能因为删除了结点，让这颗二叉排序树变得不满足二叉排序树的性质，所以对于二叉排序树的删除存在三种情况：

 

假设要删除的结点为*p(p为指向要删除结点的指针)，其双亲结点为*f，不失一般性，可设*p是*f的左孩子。

（1）若*p结点为叶子结点，即PL和PR均为空，则只需修改f->left为空即可；

（2）若*p结点只有左子树PL或者只有右子树PR，这只需令PL和PR直接成为f的左孩子即可；

（3）若*p结点的左子树和右子树均不为空，在删去*p之后，为保持其他元素之间的相对位置不变，可以有两种做法：

　　（3.1）做法一：令*s为*p的左子树PL的最右结点，则令*p的左子树PL为*f的左子树，*p的右子树PR为*s的右子树；

　　（3.2）做法二：令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删除它的直接前驱（或直接后继）。

 

对于要删除的结点同时存在左右子树的情况的解决办法

核心思想：将它的直接前驱或者直接后继作为删除结点的数据

实现方法：

 

• 如图，要删除的结点为47

• 47的直接前驱是37，直接后继是48

• 如果用直接前驱37作为删除后结点的值，（由于结点37有一个左子树）那么（左子树）36就去替换到37结点上。

• 如果用直接后继48作为删除后结点的值，（由于结点48是叶子结点）那么直接将48替换到37结点上即可。

   

  

  

 

 

 

性能分析

 

二叉排序树通常采用二叉链表作为存储结构。中序遍历二叉排序树可得到一个依据关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即是对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。

 

对于二叉排序树的查找，走的是根结点到要查找结点的路径，其比较次数等于给定值的结点在二叉排序树的层次。

使用二叉排序树进行查找，最好的情况是二叉排序树的形态和折半查找的判定树相同，搜索、插入、删除的时间复杂度等于树高，其平均查找长度和 logn 成正比，即（O(log2(n))）。

最坏情况下，当先后插入的关键字有序时，构成的二叉排序树为一棵斜树，树的深度为n，其平均查找长度为(n + 1) / 2。也就是时间复杂度为O(n)，等同于顺序查找（数列有序，树退化成线性表，如右斜树）。

 

因此，如果希望对一个集合按二叉排序树查找，最好是要对排序树进行一些必要的优化，如下：

加权平衡树(WBT)
AVL树 (平衡二叉树)
红黑树
Treap(Tree+Heap)
这些均可以使查找树的高度为 ：O(log（n）)。
 

 

二叉排序树总结

 

二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点。只要找到合适的插入和删除位置后，仅需要修改链接指针即可。插入删除的时间性能比较好。

二叉排序树既拥有类似于折半查找的特性，又采用了链表作存储结构，因此是动态查找表的一种适宜表示。

 

 

 

代码

 

typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
 
#include<malloc.h> /* malloc()等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<process.h> /* exit() */
 
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2 
 
/* 对两个数值型关键字的比较约定为如下的宏定义 */
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
 
 
 
#define N 10 /* 数据元素个数 */
typedef int KeyType; /* 设关键字域为整型 */
typedef struct
{
	KeyType key;
	int others;
} ElemType; /* 数据元素类型 */
 
typedef ElemType TElemType;
 
/* ----------------------------     二叉树的二叉链表存储表示    -------------------------------*/
 
typedef struct BiTNode
{
	TElemType data;
	struct BiTNode *lchild, *rchild; /* 左右孩子指针 */
}BiTNode, *BiTree;
 
/* ---------------------------------------------------------------------------------------------*/
 
 
/* --------------------------------   动态查找表(二叉排序树)的基本操作(8个)   -------------------------------*/
 
 
Status InitDSTable(BiTree *DT) 
{ /* 操作结果: 构造一个空的动态查找表DT */
	*DT = NULL;
	return OK;
}
 
void DestroyDSTable(BiTree *DT) 
{ /* 初始条件: 动态查找表DT存在。操作结果: 销毁动态查找表DT */
	if (*DT) /* 非空树 */
	{
		if ((*DT)->lchild) /* 有左孩子 */
			DestroyDSTable(&(*DT)->lchild); /* 销毁左孩子子树 */
		if ((*DT)->rchild) /* 有右孩子 */
			DestroyDSTable(&(*DT)->rchild); /* 销毁右孩子子树 */
		free(*DT); /* 释放根结点 */
		*DT = NULL; /* 空指针赋0 */
	}
}
 
BiTree SearchBST(BiTree T, KeyType key)
{ /* 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素， */
  /* 若查找成功，则返回指向该数据元素结点的指针,否则返回空指针。算法9.5(a) */
	if ((!T) || EQ(key, T->data.key))
		return T; /* 查找结束 */
	else if LT(key, T->data.key) /* 在左子树中继续查找 */
		return SearchBST(T->lchild, key);
	else
		return SearchBST(T->rchild, key); /* 在右子树中继续查找 */
}
 
void SearchBST1(BiTree *T, KeyType key, BiTree f, BiTree *p, Status *flag) /* 算法9.5(b)改 */
{ /* 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找 */
  /* 成功，则指针p指向该数据元素结点，并返回TRUE，否则指针p指向查找路径上 */
  /* 访问的最后一个结点并返回FALSE,指针f指向T的双亲，其初始调用值为NULL */
	if (!*T) /* 查找不成功 */
	{
		*p = f;
		*flag = FALSE;
	}
	else if EQ(key, (*T)->data.key) /*  查找成功 */
	{
		*p = *T;
		*flag = TRUE;
	}
	else if LT(key, (*T)->data.key)
		SearchBST1(&(*T)->lchild, key, *T, p, flag); /* 在左子树中继续查找 */
	else
		SearchBST1(&(*T)->rchild, key, *T, p, flag); /*  在右子树中继续查找 */
}
 
Status InsertBST(BiTree *T, ElemType e)
{ /* 当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE， */
  /* 否则返回FALSE。算法9.6(改) */
	BiTree p, s;
	Status flag;
	SearchBST1(T, e.key, NULL, &p, &flag);
	if (!flag) /* 查找不成功 */
	{
		s = (BiTree)malloc(sizeof(BiTNode));
		s->data = e;
		s->lchild = s->rchild = NULL;
		if (!p)
			*T = s; /* 被插结点*s为新的根结点 */
		else if LT(e.key, p->data.key)
			p->lchild = s; /* 被插结点*s为左孩子 */
		else
			p->rchild = s; /* 被插结点*s为右孩子 */
		return TRUE;
	}
	else
		return FALSE; /* 树中已有关键字相同的结点，不再插入 */
}
 
void Delete(BiTree *p)
{ /* 从二叉排序树中删除结点p，并重接它的左或右子树。算法9.8 */
	BiTree q, s;
	if (!(*p)->rchild) /* 右子树空则只需重接它的左子树（待删结点是叶子也走此分支） */
	{
		q = *p;
		*p = (*p)->lchild;
		free(q);
	}
	else if (!(*p)->lchild) /* 只需重接它的右子树 */
	{
		q = *p;
		*p = (*p)->rchild;
		free(q);
	}
	else /* 左右子树均不空 */
	{
		q = *p;
		s = (*p)->lchild;
		while (s->rchild) /* 转左，然后向右到尽头（找待删结点的前驱） */
		{
			q = s;
			s = s->rchild;
		}
		(*p)->data = s->data; /* s指向被删结点的＂前驱＂（将被删结点前驱的值取代被删结点的值） */
		if (q != *p)
			q->rchild = s->lchild; /* 重接*q的右子树 */
		else
			q->lchild = s->lchild; /* 重接*q的左子树 */
		free(s);
	}
}
 
Status DeleteBST(BiTree *T, KeyType key)
{ /* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点， */
  /* 并返回TRUE；否则返回FALSE。算法9.7 */
	if (!*T) /* 不存在关键字等于key的数据元素 */
		return FALSE;
	else
	{
		if EQ(key, (*T)->data.key) /* 找到关键字等于key的数据元素 */
			Delete(T);
		else if LT(key, (*T)->data.key)
			DeleteBST(&(*T)->lchild, key);
		else
			DeleteBST(&(*T)->rchild, key);
		return TRUE;
	}
}
 
void TraverseDSTable(BiTree DT, void(*Visit)(ElemType))
{ /* 初始条件: 动态查找表DT存在，Visit是对结点操作的应用函数 */
  /* 操作结果: 按关键字的顺序对DT的每个结点调用函数Visit()一次且至多一次 */
	if (DT)
	{
		TraverseDSTable(DT->lchild, Visit); /* 先中序遍历左子树 */
		Visit(DT->data); /* 再访问根结点 */
		TraverseDSTable(DT->rchild, Visit); /* 最后中序遍历右子树 */
	}
}
 
/* --------------------------------------------------------------------------------------------------*/
 
 
 
 
void print(ElemType c)
{
	printf("(%d,%d) ", c.key, c.others);
}
 
void main()
{
	BiTree dt, p;
	int i;
	KeyType j;
	ElemType r[N] = { {45,1},{12,2},{53,3},{3,4},{37,5},{24,6},{100,7},{61,8},{90,9},{78,10} }; /* 以教科书图9.7(a)为例 */
	InitDSTable(&dt); /* 构造空表 */
	for (i = 0; i < N; i++)
		InsertBST(&dt, r[i]); /* 依次插入数据元素 */
	TraverseDSTable(dt, print);
	printf("\n请输入待查找的值: ");
	scanf("%d", &j);
	p = SearchBST(dt, j);
	if (p)
	{
		printf("表中存在此值。");
		DeleteBST(&dt, j);
		printf("删除此值后:\n");
		TraverseDSTable(dt, print);
		printf("\n");
	}
	else
		printf("表中不存在此值\n");
	DestroyDSTable(&dt);
}

运行结果：