[查找] 2 二叉排序树

【二叉排序树】

二叉排序树可以是空树节点p，它的左子树比它小，它的右子树比它大

【说明】

折半查找法的判断树就是一颗二叉排序树对二叉排序树进行中序遍历，得到递减有序的序列

【基本操作】查找、插入、构建

typedef struct BTNode{
	int key;  //关键字
	struct BTNode *lchild;
	struct BTNOde *rchild;
}BiTNode, *BiTree;
// 查找的算法
BiTNode* BSTSearch(BiTree T, int key) {
	if (T) {
		if (T->key == key) return bt;
		else if ( key< T->key ) return BSTSearch(T->lchild, key);
		else return BSTSearch(T->rchild, key);
	}
}
// 插入
int BSTInsert(BiTree *pT, int key) {
	if ( (*pT)==NULL ) {
		*pT = (BiTNode *)malloc(sizeof(BiTNode)); if ( !*pT ) exit(0);
		(*pT)->key = key; (*pT)->lchild = (*pT)->rchild = NULL;
		return 1;
	} else {
		if ( (*pT)->key == key ) return 0;
		else if ( (*pT)->key > key ) return BSTInsert( &(*pT)->lchild, key);
		else return BSTInsert( &(*pT)->rchild, key);
	}
}
// 构建算法
void CreateBST(BiTree *pT, int key[], int n) {
	int i;
	*pT = NULL;
	for (i=0; i<n; i++) BSTInsert(pT, key[i]);
}

【删除】二叉排序树有约束条件，删除时切记，需要分类讨论（这里选用的是更好理解的方式）

假设删除节点p，f是p的爸爸

【情况1】p为叶子结点：直接删除p【情况2】p只有一个孩子：将p删除，用p的孩子替换p【情况3】p有两个孩子【第一步】p的关键字要删除，找一个结点r把p的位置顶上，结点r有两种找法【第二步】把r的关键字替换掉p的关键字（完成了p的删除）：r->key = p->key【第三步】删除r结点（删除r的之后，肯定属于第1、2种情况的一种）

// 删除关键字key
int DeleteBST(BiTree *pT, int key) {
	// 先查找到key，然后调用进行删除
	if ( *pT ) {
		if ( (*pT)->key == key ) return Delete(pT); //找到关键字
		else if ( (*pT)->key > key ) return DeleteBST( &(*pT)->lchild, key);
		else return DeleteBST( &(*pT)->rchild, key);
	}
}
// 删除操作
int Delete(BiTree *pT) {
	BiTNode *q, *r;
	if ( (*pT)->lchild==NULL && (*pT)->rchild==NULL ) { //情况一
		q = *pT;
		*pT = NULL;
		free(q);
	} else if ( (*pT)->lchild && (*pT)->rchild ) { //情况三
		r = (*pT)->lchild; //往左走一步
		wihle (r->rchild) { //再往右走到尽头
			r = r->rchild;
		}
		(*pT)->key = r->key; //r结点的key替换p，完成p关键字的删除
		return Delete( &r ); //删除r结点：一定是情况一、情况二，不会出现循环调用
	} else { //情况二
		q = *pT;
		*pT = (*pT)->lchild==NULL ? (*pT)->rchild : (*pT)->lchild; // 左子树为空 ? 挂上右子树 ： 挂上左子树
		free(q);
	}
	return TRUE;
}

名称说明图

二叉排序树

有时候会很低效（ASL=(1+2+3+4+5)/5=3，和没有建树一样）

平衡二叉树

为了不让它那么长c语言二叉排序树，边的扁一点矮一点胖一点，改进出了平衡二叉树（ASL=(1+2+2+3+3)/5=2.2）

【约束条件】二叉排序树的演化，所有节点的左右子树高度之差的绝对值≤1

【平衡二叉树（AVL树）】一种特殊的二叉排序树，其左右子树都是平衡二叉树，且左右子树高度之差绝对值≤1

【定量判断】结点p，平衡因子=p左子树高度-p右子树高度，平衡因子的绝对值≤1

图中每个节点旁的数字代表该节点的平衡因子

【平衡调整】|平衡因子|＞1的节点即丧失平衡，要进行平衡调整

【原理】

当失去平衡的最小子树被调整为平衡子树后，无需调整原有其他所有不平衡子树，整个二叉排序树就会变成一颗平衡二叉树【失去平衡的最小子树】是以距离插入节点最近，且平衡因子绝对值大于1的节点作为根的子树

【步骤】

插入新节点插入后，找出失去平衡的最小子树调整这棵子树，使之成为平衡子树

【调整的四种情况】LL型、RR型、LR型、RL型

名字名字解释说明图例

LL(Left-Left)调整

右单旋转调整

在根(A)的左孩子(B)的左子树上插入节点，发生了不平衡

1. A往下翻转一个位置，变成B的右孩子结点

2. B的右子树挂在A的左子树上

RR(Right-Right)调整

左单旋转调整

在根(A)的右孩子(B)的右孩子上插入了结点，所出现的不平衡（是LL情况的对称情况）

1. A往下翻转一个位置，变成B的左孩子

2. 将B的左孩子挂在A的右孩子上

LR调整

先左后右双旋转调整

在根结点(A)左孩子(B)的右子树上插入节点，导致不平衡

1. 把B整体摘出来，变成了RR的情况

2. 对B整体进行RR调整

3. 挂载A结点的空指针上c语言二叉排序树，变成了LL的情况

4. 对A整体进行LL调整

RL调整

先右后左双旋转调整

根结点(A)的右孩子的左子树上插入节点，导致的不平衡（是LR调整的对称状况）

1. 把B整体摘出来，变成了LL的情况

2. 对B整体进行LL调整

3. 挂在A结点的空指针上，变成了RR的情况

4. 对A进行RR调整

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-122006-1.html