二叉搜索树和平衡二叉搜索树应用
程序员文章站
2022-05-06 22:50:23
...
1、树的基本术语
（1） 结点的度：树中一个结点的子节点个数称为结点的度
（2）树的度：树中结点的最大度数称为树的度
（3）分支结点：度大于0的结点（又称为非终端结点）
（4）叶子结点：度等于0（没有子女结点）的结点称为叶子结点。
（5）结点的层次：从树根开始定义，根结点为第一层 （有的也把根结点当为第0层）
（6）结点的深度：是从根节点开始自顶向下逐层累加的
（9）路径和路径长度：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的。路径长度是路径上所经过的边的个数。
（10）有序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树是有序数，否则称为无序树
（11）森林：是m（>=0）棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的跟删除就成了森林。
（2）树的度：树中结点的最大度数称为树的度
（3）分支结点：度大于0的结点（又称为非终端结点）
（4）叶子结点：度等于0（没有子女结点）的结点称为叶子结点。
（5）结点的层次：从树根开始定义，根结点为第一层 （有的也把根结点当为第0层）
（6）结点的深度：是从根节点开始自顶向下逐层累加的
（7）结点的高度：从根节点开始自底向上逐层累加
（8）树的高度（又叫深度）：是树中结点的最大层数 （9）路径和路径长度：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的。路径长度是路径上所经过的边的个数。
（10）有序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树是有序数，否则称为无序树
（11）森林：是m（>=0）棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的跟删除就成了森林。
2、二叉树的分类
（1）满二叉树：从高到低，除了叶节点外，所以节点左右节点都存在。
（2）完全二叉树：比满二叉树少几个叶节点，从左向右放子节点。
（3）平衡二叉树：空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树也都是平衡树。
（4）二叉搜索树：空树或者二叉树的所有节点比他的左子节点大，比他的右子节点小。
（5）红黑树：不仅是具有二叉搜索树的属性，还具有平衡树的属性，有序且子树差不超过1，颜色规则：根节点和特殊节点（即叶节点下面两个虚无的节点和未填写的节点）是黑的，红节点的左右子节点是黑的，最重要的是对于每个节点，从该节点到子孙叶节点的所有路径包含相同数目的黑节点。
3、二叉树的遍历方式
3种遍历方式规律
父结点为中，左右子结点为左和右，遍历方式的命名规则是遍历时父结点的位置，左右顺序不变，先左后右。
前序遍历（中-左-右）：17 12 10 8 11 15 13 16 19 18 25 22
中序遍历（左-中-右）：8 10 11 12 13 15 16 17 18 19 22 25
后序遍历（左-右-中）：8 11 10 13 16 15 12 18 22 25 19 17
4、二叉搜索树
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：
① 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
② 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
③ 它的左、右子树也分别为二叉排序树。
对二叉搜索树进行中序遍历，可以得到一个递增的有序序列。
4.1、二叉搜索树的各项操作
①查找结点
// 查找，平均查找复杂度O(lgN)
template<typename T>
bool BinarySearchTree<T>::ContainsRecu(BinaryTreeNode* root, const T& val) const
{
if (root == NULL) // 如果树为空，则查找失败
{
return false;
}
else if (val > root->data) // 如果值大于根节点关键字的值，递归查找右子树
{
return Contains(root->right, val);
}
else if (val < root->data) // 如果值小于根节点关键字的值，递归查找左子树
{
return Contains(root->left, val);
}
else // 如果根节点关键字的值等于查找的关键字，成功
{
return true;
}
}②获得最小值
// 获取最小值，时间复杂度O(lgN)
template <typename T>
BinarySearchTree::BinaryTreeNode* BinarySearchTree<T>::FindMin(BinaryTreeNode* &p) const
{
while (p != NULL && p->left != NULL) // 从根节点开始一直往左走，直到无路可走。
{
p = p->left;
}
return p;
}③获得最大值
// 获取最大值，时间复杂度O(lgN)
template <typename T>
BinarySearchTree::BinaryTreeNode* BinarySearchTree<T>::FindMin(BinaryTreeNode* &p) const
{
while (p != NULL && p->left != NULL) // 从根节点一直往右走，直到无路可走
{
p = p->left;
}
return p;
}④插入操作
// 插入结点，时间复杂度O（lgN)
template<typename T>
void BinarySearchTree<T>::Insert(BinaryTreeNode* &p, const T& val)
{
// 注意：新插入的节点总是叶子节点，如果树种有相同的节点，则不做任何操作。
if (p == NULL) // 一直到尾端，即为插入点
{
p = new BinaryTreeNode(val);
}
else if (val > p->data) // 遇键值较小者就向右
{
Insert(p->right, val);
}
else if (val < p->data) // 遇键值较大者就向左
{
Insert(p->left, val);
}
else
; //重复，不做任何操作
}⑤删除操作
（1）目标结点只有一个子结点的删除操作
（2）目标结点有两个子结点的删除操作
// 删除结点，时间复杂度O(lgN)
template<typename T>
void BinarySearchTree<T>::Remove(BinaryTreeNode* &p, const T& val)
{
if (p == NULL)
{
return; //没有此值
}
else if (val > p->data) // 遇键值较小者就向右
{
Remove(p->right, val);
}
else if (val < p->data) // 遇键值较大者就向左
{
Remove(p->left, val);
}
// 如果节点有两个子节点，一般的删除策略是用其右子树的数据代替该节点的数据并递归地的删除那个节点
else if (p->left != NULL && p->right != NULL) 。
{
p->data = FindMin(p->right)->data;
Remove(p->right, val);
}
else // 如果节点有一个儿子，则该节点可以再其父节点调整它的链绕过该节点后被删除。
{
BinaryTreeNode* oldNode = p;
p = (p->left != NULL) ? p->left : p->right;
delete oldNode;
}
}⑥复制
// 复制
template<typename T>
typename BinarySearchTree<T>::BinaryTreeNode* BinarySearchTree<T>::Clone(BinaryTreeNode* root)
{
if (root == NULL)
{
return NULL;
}
return new BinaryTreeNode(root->val, Clone(root->left), Clone(root->right));
}⑦清空
// 清空
template<typename T>
void BinarySearchTree<T>::MakeEmpty(BinaryTreeNode* root)
{
if (root != NULL)
{
MakeEmpty(root->left);
MakeEmpty(root->right);
delete root;
}
root = NULL;
}5、平衡二叉树（AVL树）
衡量二叉搜索树搜索效率的标准：平均查找长度(ASL):每个结点比较次数和/结点数
平衡因子（BF）：左子树的高度减去右子树的高度。
判断一个二叉搜索树是否为一个平衡二叉树：|BF|小于等于1
当对一个平衡二叉树插入一个结点后，AVL树就变的不平衡了
平衡二叉树的调整：分为四种情况
（1）插入点位于X的右子结点的右子树：RR插入，需要RR旋转
（2）插入点位于X的左子结点的左子树：LL插入，需要LL旋转
（3）插入点位于X的右子结点的左子树：RL插入，需要RL旋转
（3）插入点位于X的左子结点的右子树：LR插入，需要LR旋转
①RR调整
调整的演示图
上面的不平衡的搜索树的发现者是Mar，麻烦节点是Nov，Nov在发现者的右子树的右边，因而叫做RR插入，需要进行RR旋转(右单旋)
RR调整的通解图：
/*
右单旋:将A与B进行RR旋转，并更新A与B的高度,返回新的根节点B
注：A必须有一个右节点B
*/
pTree singleRightRatation(pTree A)
{
pTree B = A->right;
A->right = B->left;
B->left = A;
A->treeHeight = getMaxValue(getHeight(A->left),getHeight(A->right))+1;
B->treeHeight = getMaxValue(getHeight(B->right),A->treeHeight);
return B;
}②LL调整
LL调整的演示图：
发现者Mar，麻烦节点为Apr在发现者的左子树的左边，因而叫LL插入，需要LL旋转
LL调整的通解图：
/*
左单旋操作：将A与B进行LL旋转，并更新A和B的新高度，返回新的根节点B
A必须有一个左子节点B
*/
pTree singleLeftRatation(pTree A)
{
pTree B = A->left;
A->left=B->right;
B->right = A;
A->treeHeight = getMaxValue(getHeight(A->left),getHeight(A->right))+1;
B->treeHeight = getMaxValue(B->left,A->treeHeight)+1;
return B;
}③LR调整
LR调整的演示图
发现节点是May，麻烦节点是Jan，Jan在May左子树的右子树中，因而叫做LR插入，需要进行LR旋转
LR调整的通解图：
/*
将A做LR旋转，返回新的根节点C
A必须有一个左自己的B，B必须有一个右子节点C
*/
pTree doubleLeftRightRatation(pTree A)
{
/*先对B，C进行RR旋转,C被返回*/
A->left = singleRightRatation(A->left);
/*在对A和C进行LL旋转，返回新的根节点C*/
return singleLeftRatation(A);
}④RL调整
RL调整的演示图：
发现节点是Aug，麻烦节点是Feb，Feb在Aug的右子树的左子树上面，因而叫做RL插入，需要进行RL旋转
RL调整的通解图：
/*
对A进行RL旋转，返回新的根节点C
注：A必须有一个右子节点B，B必须有一个左子节点C
*/
pTree doubleRightLeftRatation(pTree A)
{
/*先对B，C进行LL旋转,返回新的根节点C*/
A->right = singleLeftRatation(A->right);
/*在对A，C进行RR旋转，返回新的根节点C*/
return singleRightRatation(A);
}完整AVL tree实作和测试代码
#include<stdio.h>
#include<stdlib.h>
typedef int elementType;
/*define a binary tree*/
typedef struct node{
elementType element;
struct node *left;
struct node *right;
int treeHeight;/*为了平衡二叉树计算方便，定义树高*/
}tre,*pTree;
/*二叉搜索树的递归查找*/
pTree find(elementType element,pTree tree){
if(!tree){
return NULL;
}
if(element<tree->element){
/*查找元素比根元素小在左子树中查找*/
return find(element,tree->left);
}else if(element>tree->element){
/*查找元素比根元素小在右子树中查找*/
return find(element,tree->right);
}else{/*找到该节点，返回*/
return tree;
}
}
/*因为递归方法执行的效率低，而且上面的尾递归函数可以改写为递归函数*/
pTree find2(elementType element,pTree tree){
pTree temp;
temp = tree;
while(temp){
if(element<temp->element){
temp=temp->left;
}else if(element>temp->element){
temp=temp->right;
}else{
return temp;
}
}
return NULL;
}
/*根据二叉搜索树的特点，最小元素在最左边的节点上面*/
pTree getMinElement(pTree tree){
if(tree){
while(tree->left){
tree=tree->left;
}
}
return tree;
}
/*获取二叉搜索树中的最大元素，最大元素的位置应该在最右边的节点上*/
pTree getMaxElement(pTree tree){
if(tree){
while(tree->right){
tree = tree->right;
}
}
return tree;
}
/*二叉搜索树的插入，知识遵循二叉搜索树的性质，但是并没有调节平衡*/
pTree insert(pTree tree,elementType element){
pTree temp;
if(!tree){
tree = (pTree)malloc(sizeof(tre));
tree->element=element;
tree->left=tree->right=NULL;
}else{/**/
if(element<tree->element){
tree ->left = insert(tree->left,element);
}
else if(element>tree->element){
tree->right = insert(tree->right,element);
}
}
return tree;
}
/*非递归的二叉搜索树的算法*/
pTree insert2(pTree tree,elementType element){
pTree temp;
int flag;
pTree parent;
if(!tree){
tree = (pTree)malloc(sizeof(tre));
tree->element=element;
tree->left=tree->right=NULL;
}else{
temp=tree;
while(temp!=NULL){
if(element<temp->element){
//printf("lala\n");
parent = temp;
temp=temp->left;
flag=0;
}else if(element>temp->element){
parent = temp;
flag=1;
temp=temp->right;
}
}
temp = (pTree)malloc(sizeof(tre));
temp->element=element;
temp->left=temp->right=NULL;
if(flag){
parent->right=temp;
}else{
parent->left=temp;
}
}
return tree;
}
/*在二叉搜索树中删除一个元素
算法思想：
1.首先查找到该元素
2.如果该元素是叶子节点，直接删除
3.如果该元素有一个孩子节点，直接把孩子节点挂载到该节点的父节点上
4.如果该节点有两个孩子，由两种方法
a.在该节点的左子树中找到最大元素节点T，把该节点的值替换成T的值，然后执行对T的删除操作
b.在该节点的右子树中找最小元素的节点T，把该节点的值替换为T的值，然后执行对T的删除操作
注：找最大或者最小元素是因为最大最小元素是叶子节点或者只有一个孩子。
*/
pTree deleteElement(pTree tree,elementType element){
pTree temp;
if(!tree){
printf("the element don't search in this tree\n");
}else if(element<tree->element){
tree->left=deleteElement(tree->left,element);
}else if(element>tree->element){
tree->right = deleteElement(tree->right,element);
}else{//找到需要删除的元素节点
if(tree->left && tree->right){//该有两个孩子节点
temp = getMinElement(tree->right);/*获取右子树的最小值节点*/
tree->element=temp->element;
tree->right=deleteElement(tree->right,temp->element);
}else{
temp=tree;
if(!tree->left){
tree=tree->right;
}else if(!tree->right){
tree=tree->left;
}
free(temp);
}
}
return tree;
}
/*使用非递归的方法
pTree deleteElement2(pTree tree,elementType element){
pTree temp,maxSubNode,flag,temp2;
if(!tree){
printf("the tree is empty,don't allow delete elememt\n");
}else{
temp = find(element,tree);
if(temp==NULL){
printf("the element don't exsit in this tree\n");
}else{
if(temp->left && temp->right){
maxSubNode = getMinElement(temp->right);
temp->element = maxSubNode->element;
}else{
maxSubNode = temp;
}
temp2=maxSubNode;
if(!maxSubNode->left){
maxSubNode=maxSubNode->right;
}else if(!maxSubNode->right){
maxSubNode=maxSubNode->left;
}
free(temp2);
}
}
return tree;
}*/
//先序遍历
void preOrderTraversal(pTree tree){
if(tree){
printf("%d ",tree->element);
preOrderTraversal(tree->left);
preOrderTraversal(tree->right);
}
}
/*=====================================调整树为平衡二叉树===============================================*/
int getMaxValue(int a,int b){
return a > b ? a : b ;
}
/*获取二叉树的树高*/
int getHeight(pTree tree){
int leftHeight,rightHeight;
if(tree){
leftHeight = getHeight(tree->left);
rightHeight = getHeight(tree->right);
return (leftHeight>rightHeight ? leftHeight : rightHeight)+1;
}
return 0;
}
/*
左单旋操作：将A与B进行LL旋转，并更新A和B的新高度，返回新的根节点B
A必须有一个左子节点B
*/
pTree singleLeftRatation(pTree A){
pTree B = A->left;
A->left=B->right;
B->right = A;
A->treeHeight = getMaxValue(getHeight(A->left),getHeight(A->right))+1;
B->treeHeight = getMaxValue(B->left,A->treeHeight)+1;
return B;
}
/*右单旋:将A与B进行RR旋转，并更新A与B的高度,返回新的根节点B
注：A必须有一个右节点B
*/
pTree singleRightRatation(pTree A){
pTree B = A->right;
A->right = B->left;
B->left = A;
A->treeHeight = getMaxValue(getHeight(A->left),getHeight(A->right))+1;
B->treeHeight = getMaxValue(getHeight(B->right),A->treeHeight);
return B;
}
/*
将A做LR旋转，返回新的根节点C
A必须有一个左自己的B，B必须有一个右子节点C
*/
pTree doubleLeftRightRatation(pTree A){
/*先对B，C进行RR旋转,C被返回*/
A->left = singleRightRatation(A->left);
/*在对A和C进行LL旋转，返回新的根节点C*/
return singleLeftRatation(A);
}
/*
对A进行RL旋转，返回新的根节点C
注：A必须有一个右子节点B，B必须有一个左子节点C
*/
pTree doubleRightLeftRatation(pTree A){
/*先对B，C进行LL旋转,返回新的根节点C*/
A->right = singleLeftRatation(A->right);
/*在对A，C进行RR旋转，返回新的根节点C*/
return singleRightRatation(A);
}
/*对二叉搜索树进行插入，插入后调整树的平衡*/
pTree AVLInsert(pTree tree,elementType element){
if(!tree){
tree = (pTree)malloc(sizeof(tre));
tree->element = element;
tree->left=tree->right = NULL;
tree->treeHeight=0;
}else if(element<tree->element){
tree->left = AVLInsert(tree->left,element);
//判断平衡因子是否等于2
if(getHeight(tree->left)-getHeight(tree->right) == 2){
if(element<tree->left->element){//element往tree的左子树的左子树插入导致平衡因子大于2，进行LL调整的
tree = singleLeftRatation(tree);
}else{//element往tree的左子树的右子树插入导致平衡因子大于2，进行LR调整
tree = doubleLeftRightRatation(tree);
}
}
}else if(element>tree->element){
tree->right = AVLInsert(tree->right,element);
//判断平衡因子是否等于2
if(getHeight(tree->right)-getHeight(tree->left) == 2){
if(element>tree->right->element){//element往tree的右子树的右子树插入导致平衡因子大于2，进行RR调整
tree = singleRightRatation(tree);
}else{//element往tree的右子树的左子树插入导致平衡因子大于2，进行RL调整
tree = doubleRightLeftRatation(tree);
}
}
}/* else 如果找到了，就不进行插入*/
tree->treeHeight = getMaxValue(getHeight(tree->left),(getHeight(tree->right)))+1;
return tree;
}
void main(){
printf("\n==========普通插入=====================================\n");
int findElement=33;
int deleteData=41;
pTree tree=insert(NULL,30);
tree=insert(tree,15);
tree=insert(tree,41);
tree=insert(tree,33);
tree=insert(tree,50);
tree=insert(tree,35);
preOrderTraversal(tree);
printf("\n");
printf("The find element is:%d,the result is %d \n",findElement,find(findElement,tree)->element);
printf("The min element:%d\n",getMinElement(tree)->element);
printf("The max element:%d\n",getMaxElement(tree)->element);
//printf("delete the elemet %d\n",deleteData);
//deleteElement(tree,deleteData);
printf("\nordinary tree preOrder\n");
preOrderTraversal(tree);
printf("\n==========AVL插入=====================================\n");
pTree AVLTree=AVLInsert(NULL,30);
AVLTree=AVLInsert(AVLTree,15);
AVLTree=AVLInsert(AVLTree,41);
AVLTree=AVLInsert(AVLTree,33);
AVLTree=AVLInsert(AVLTree,50);
AVLTree=AVLInsert(AVLTree,35);
printf("\n");
printf("The find element is:%d,the result is %d \n",findElement,find(findElement,AVLTree)->element);
printf("The min element:%d\n",getMinElement(AVLTree)->element);
printf("The max element:%d\n",getMaxElement(AVLTree)->element);
//printf("delete the elemet %d\n",deleteData);
//deleteElement(AVLTree,deleteData);
printf("\nAVL tree preOrder\n");
preOrderTraversal(AVLTree);
}
来源：https://www.cnblogs.com/yghjava/p/6715732.html
上一篇： vue的父组件，子组件的一图详解
下一篇： 重构初体验——影片出租店例子