5、二叉搜索树与平衡二叉树（BST & AVL）

一、二叉搜索树

1.二叉搜索树是什么

二叉搜索树（BST，Binary Search Tree),又称二叉排序树或二叉查找树，是一棵二叉树，可以为空，当不为空时满足以下性质：

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

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

• 左、右子树都为二叉搜索树

2.二叉搜索树的操作函数

(1)二叉搜索树的查找操作Find

要查找的值为X

• 从根结点开始查找，若树为空，则返回NULL

• 若搜索树非空，则将X与根节点的键值进行比较并进行以下处理

  1. 若X小于根结点键值，则在左子树中搜索

  2. 若X大于根结点键值，则在右子树中搜索

  3. 若X与根结点键值相等，则搜索完成，返回指向该结点的指针

尾递归实现

Position Find(ElementType X, BinTree BST) {
	if( !BST ) return NULL;//查找失败
	if( X > BST->Data )
		return Find(X, BST->Right);//操作1
	else if (X < BST->Data) 
		return Find(X, BST->Left); //操作2
	else 
		return BST; //操作3 查找成功
}

迭代函数实现

Position Find(ElementType X, BinTree BST) {
	while(BST) {
		if (X > BST->Data)
			BST = BST->Right;//操作1
		else if (X < BST->Data)
			BST = BST->Left;//操作2
		else 
			return BST;//操作3 查找成功
	}
	return NULL;//查找失败
}

(2)查找最大元素和最小元素

• 最大元素一定是在树的最右分支的端结点上

• 最小元素一定是在树的最左分支的端结点上

查找最大元素

递归函数

Position FindMin(BinTree BST) {
	if (!BST ) return NULL;//空树，返回NULL
	else if ( !BST->Left )
		return BST;	//找到了最左叶结点
	else 
		return FindMin(BST->Left);//沿左分支继续查找
}

迭代函数

Position FindMin(BinTree BST) {	
	if (BST) {
		while (BST->Left)	BST = BST->Left;
	}
	return BST;
}

查找最小元素

递归函数

Position FindMax(BinTree BST) {
	if (!BST ) return NULL;//空树，返回NULL
	else if ( !BST->Right )
		return BST;	//找到了最左叶结点
	else 
		return FindMin(BST->Right);//沿右分支继续查找
}

迭代函数

Position FindMax(BinTree BST) {	
	if (BST) {
		while (BST->Right)	BST = BST->Right;
	}
	return BST;
}

(3)二叉搜索树的插入

要保证插入后还为二叉搜索树，关键时要找到元素应该插入的位置。

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 printf("该值已存在"); 
	}
	return BST;
}

(4)二叉搜索树的删除

考虑三种情况

• 要删除的是叶结点：直接删除，并修改其父结点的指针

• 要删除的结点只有一个孩子结点：将其父节点的指针指向要删除结点的孩子结点
• 要删除的结点有左、右两棵子树:要用另一个结点替代被删除的结点（右子树的最小元素或左子树的最大元素）

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 {	//待删除结点有1个或无子结点
			Tmp = BST;
			if (!BST->Left) //有有孩子或无子节点
				BST = BST->Right;
			else if (!BST->Right)
				BST = BST->Left;
			free(Tmp);
		}
	}
	return BST;
}

二、平衡二叉树

1.平衡二叉树是什么

平衡二叉树（AVL树，Banlanced Binary Tree ),可以为空，当不为空时满足以下性质：

• 任一结点左、右子树高度差的绝对值不超过1

• 给定结点数为n的AVL树的最大高度为O(log2n)!

平衡因子（BF,Banlanced Factor）:BF(T) = hL-hR,hL和hR分别为T的左、右子树高度

2.平衡二叉树的调整

RR插入——RR旋转【右单旋】

破坏结点（麻烦结点）位于被破坏结点（发现者）的右子树的右子树上

LL插入——LL旋转【左单旋】

破坏结点（麻烦结点）位于被破坏结点（发现者）的左子树的左子树上

LR插入——LR旋转

破坏结点（麻烦结点）位于被破坏结点（发现者）的左子树的右子树上

RL插入——RL旋转

破坏结点（麻烦结点）位于被破坏结点（发现者）的右子树的左子树上

ps：有时候插入元素即便不需要调整结构，也可能需要重新计算一些平衡因子

3.平衡二叉树实现

定义部分

typedef struct AVLNode *Position;
typedef Position AVLTree;
struct AVLNode {
	ElementType Data;
	AVLTree Left, Right;
	int Height;
};
int Max(int a, int b) {
	return a>b?a:b;
}

左单旋

ps:A必须要有一个左子节点B，将A与B进行左单旋，并更新A与B的高度返回新的根结点B

AVLTree SingleLeftRotation(AVLTree A) {
	AVLTree B = A->Left;
	A->Left = B->Right;
	B->Right = A;
	A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
	B->Height = Max( GetHeight(B->Left),A->Height ) + 1;
	return B;
}

右单旋

ps:A必须要有一个右子节点B，将A与B进行右单旋，并更新A与B的高度返回新的根结点B

AVLTree SingleRightRotation(AVLTree A) {
	AVLTree B = A->Right;
	A->Right = B->Left;
	B->Left = A;
	A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
	B->Height = Max( A->Height, GetHeight(B->Right) ) + 1;
	return B;
}

LR旋转

ps:A必须要有一个左子节点B，且B必须有一个右子节点C 先将B与C做右单旋，返回C 再将A与C做左单旋，返回C

AVLTree DoubleLeftRightRotation(AVLTree A) {
	A->Left = SingleRightRotation(A->Left);
	return SingleLeftRotation(A);
}

RL旋转

ps:A必须要有一个右子节点B，且B必须有一个左子节点C 先将B与C做左单旋，返回C 再将A与C做右单旋，返回C

AVLTree DoubleRightLeftRotation(AVLTree A) {
	A->Right = SingleLeftRotation(A->Right);
	return SingleRightRotation(A);
}

插入

将X插入AVL树T中，并返回调整后的AVL树

AVLTree Insert(AVLTree T,ElementType X) {
	if (!T) {	//若要插入的树是空树，则新建一个包含结点X的树
		T = (AVLTree) malloc(sizeof(struct AVLNode));
		T->Data = X;
		T->Height = 0;
		T->Left = T->Right = NULL;
	} else if( X < T->Data) {
		T->Left = Insert(T->Left, X);
		if (GetHeight(T->Left)-GetHeight(T->Right) == 2) {//需要左旋
			if (X < T->Left->Data)
				T = SingleLeftRotation(T);	//需要左单旋
			else 
				T = DoubleLeftRightRotation(T);//左-右双旋
		}
	} else if (X > T->Data) {
		T->Right = Insert(T->Right, X);
		if (GetHeight(T->Left)-GetHeight(T->Right) == -2) {//需要右旋
			if (X > T->Right->Data)
				T = SingleRightRotation(T);	//需要右单旋
			else 
				T = DoubleRightLeftRotation(T);//右-左双旋
		}
	}
	//更新树高
	T->Height =  Max( GetHeight(T->Left),GetHeight(T->Right) ) + 1;
	return T;
}

完整代码演示

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct AVLNode *Position;
typedef Position AVLTree;
struct AVLNode {
	ElementType Data;
	AVLTree Left, Right;
	int Height;
};
int Max(int a, int b) {
	return a>b?a:b;
}
int GetHeight(AVLTree A) {
    if (A)
        return A->Height;
    else 
        return 0;
}
AVLTree SingleLeftRotation(AVLTree A) {//左单旋
	AVLTree B = A->Left;
	A->Left = B->Right;
	B->Right = A;
	A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
	B->Height = Max( GetHeight(B->Left),A->Height )+ 1;
	return B;
}
AVLTree SingleRightRotation(AVLTree A) {//右单旋
	AVLTree B = A->Right;
	A->Right = B->Left;
	B->Left = A;
	A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
	B->Height = Max( A->Height, GetHeight(B->Right) ) + 1;
	return B;
}
AVLTree DoubleLeftRightRotation(AVLTree A) {//左-右双旋
	A->Left = SingleRightRotation(A->Left);
	return SingleLeftRotation(A);
}
AVLTree DoubleRightLeftRotation(AVLTree A) {//右-左双旋
	A->Right = SingleLeftRotation(A->Right);
	return SingleRightRotation(A);
}
AVLTree Insert(AVLTree T,ElementType X) {//将X插入AVL树T中
	
	if (!T) {	//若要插入的树是空树，则新建一个包含结点X的树
		T = (AVLTree) malloc(sizeof(struct AVLNode));
		T->Data = X;
		T->Height = 0;
		T->Left = T->Right = NULL;
        
	} else if( X < T->Data) {
		T->Left = Insert(T->Left, X);
		if (GetHeight(T->Left)-GetHeight(T->Right) == 2) {//需要左旋
			if (X < T->Left->Data)
				T = SingleLeftRotation(T);	//需要左单旋
			else 
				T = DoubleLeftRightRotation(T);//左-右双旋
		}
	} else if (X > T->Data) {
		T->Right = Insert(T->Right, X);
		if (GetHeight(T->Left)-GetHeight(T->Right) == -2) {//需要右旋
			if (X > T->Right->Data)
				T = SingleRightRotation(T);	//需要右单旋
			else 
				T = DoubleRightLeftRotation(T);//右-左双旋
		}
	}
	//更新树高
	T->Height =  Max( GetHeight(T->Left),GetHeight(T->Right) ) + 1;
    return T;
}
void PreOrderTraversal(AVLTree T) {
	if(T) {
		printf("%d", T->Data);
		PreOrderTraversal( T->Left);
		PreOrderTraversal( T->Right);
	}
}
void InOrderTraversal(AVLTree T) {
	if(T) {
		InOrderTraversal( T->Left);
		printf("%d", T->Data);
		InOrderTraversal( T->Right);
	}
}
int main() {
    AVLTree T = NULL;
    int i;
    for (i = 1; i < 10; i++) {
        T = Insert(T,i);
    }
    PreOrderTraversal(T);//前序遍历
    printf("\n");
    InOrderTraversal(T);//中序遍历
    return 0;
}

输出结果：

421365879 123456789

根据前序遍历与中序遍历易还原得到这样一个平衡二叉树

在这里插入图片描述

三、判断是否同一棵二叉搜索树

题意：给定一个插入序列确定唯一一棵二叉搜索树，对于输入的各种插入序列，判断它们是否能生成一样的二叉搜索树

如何判断两个序列是否对应相同搜索树呢 建一棵树，再判别其他序列是否与该树一致！ 如输入3 1 4 2确定一颗二叉搜索树，判断3 4 1 2和 3 2 4 1是否对应同一棵树

1.搜索树表示

typedef struct TreeNode *Tree;
struct TreeNode {
	int v;
	Tree Left,Right;
	int flag;	//用来标记该结点是否已经被搜索过 为1则搜索过
};

2.建搜索树T

Tree MakeTree(int N) {
	Tree T;
	int i, V;
	scanf("%d", &V);
	T = NewNode(V);
	for(i = 1; i < N; i++) {
		scanf("%d",&V);
		T = Insert(T,V);//将剩余结点插入二叉树
	}
	return T;
}

Tree NewNode(int V) {
	Tree T = (Tree)malloc(sizeof(struct TreeNode));
	T->v = V;
	T->Left = T->Right = NULL;
	T->flag = 0;
	return T;
}

Tree Insert(Tree T, int V) {
	if(!T) T = NewNode(V);
	else {
		if (V > T->v) 
			T->Right = Insert(T->Right, V);
		else 
			T->Left = Insert(T->Left,V);
	}
	return T;
}

3.判别一序列是否与搜索树T一致

方法：在树T中按顺序搜索序列3 2 4 1中的每个数

• 若每次搜索所经过的结点在前面均搜索过，则一致

• 否则（某次搜索中遇到了前面未出现的结点），则不一致

int check(Tree T,int V) {
	if(T->flag) {//这个点查找过了,则判断要在左子树还是右子树查找
		if(V < T->v) return check(T->Left,V);
		else if(V > T->v) return check(T->Right,V);
		else return 0;
	}
	else {	//要查找的刚好是这个点，进行标记
		if(V == T->v) {
			T->flag = 1;
			return 1;
		}
		else return 0; //碰到了以前没见过的点
	}
}

判断长度为N的插入序列产生的树是否与搜索树一致

int Judge(Tree T,int N) {
	int i, V, flag = 0;//flag=0代表当前还一致，为1则说明已经不一致了
	scanf("%d",&V);
	if (V != T->v) flag = 1;
	else T->flag = 1;
	for(i = 1; i < N; i++) {
		scanf("%d", &V);
		if( (!flag) && (!check(T,V)) ) flag = 1;
	}
	if(flag) return 0;
	else return 1;
}

清除T中个结点的flag标记使其为0

void ResetT(Tree T) {
	if(T->Left) ResetT(T->Left);
	if(T->Right) ResetT(T->Right);
	T->flag = 0;
}

释放T的空间

void FreeTree(Tree T) {
	if(T->Left) FreeTree(T->Left);
	if(T->Right) FreeTree(T->Right);
	free(T);
}