技术博客
首页 所有文章 标签 分类 关于
技术博客

目录

最适合新手看的平衡二叉搜索树BBST的创建,包含详细过程,一看就会C版

 收录于 数据结构
   约 3760 字   预计阅读 8 分钟 
https://bing.ee123.net/img/rand?artid=107767231

最适合新手看的平衡二叉搜索树(BBST)的创建，包含详细过程，一看就会(C++版)

写在前面：本人大二小白，本篇文章是我第一次写博客，用来记录我的学习过程，我想将我在学习中遇到的各种的问题和困难写下来，希望大家能够不要犯同样的错误。我会尽可能的详细的把每一个步骤都解释清楚，那么废话不多说，现在开始吧。

目录

1.有关平衡搜索二叉树的相关定义和性质

(1)二叉搜索树的定义

对于二叉搜索树，我们有如下定义，它是一棵空树或者是具有以下性质的二叉树：

1.它具有普通二叉树具有的所有性质；

2.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；

3.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；

4.任何节点的左子树和右子树都是一颗二叉搜索树。

根据定义我们很容易发现二叉搜索树的中序遍历得到的结果是一个有序数组，因此二叉搜索树又叫二叉排序树(BST)。为了方便后续的相关操作，因此我们在树的结构中加入了一个父节点指针，用于指向该节点的父节点，可以自底向上迭代。

定义方式如下：

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode* parent;		//指向每个节点的父节点
    TreeNode(int x) : val(x), left(nullptr), right(nullptr), parent(nullptr){}
};

二叉搜索树示例：

https://i-blog.csdnimg.cn/blog_migrate/8439fe23917208f03853921656f30942.png

(2)平衡二叉树的定义

为什么要引入平衡二叉树的概念呢，相信大家都发现了，上图中的第二棵二叉搜索树构成链表式的树(下文会解释为什么会出现这种情况)，所以我们的查找复杂度就变成了最坏的情况O(n)，跟普通数组的遍历时间复杂度相同，起不到优化查找的目的，因此需要对树的高度进行调整。

平衡二叉树也称AVL树，AVL树本质上还是一颗二叉搜索树，只不过加了“平衡”的要求。对此，我们引入平衡二叉树的性质：

1.它具有普通二叉搜索树具有的所有性质；

2.其任意节点的左右子树的高度之差的绝对值小于等于1，并将这个差值叫做该节点的平衡因子(balancefactor)。

由定义可知，对于任何节点都有|balancefactor|<=1，因此我们可以保证每次查找的时候都是O(logn)的级别，因此我们只需要在树的结构中加一个int型变量balancefactor来记录当前节点的平衡因子。

定义方式如下：

struct TreeNode{
    int val;
    int BalanceFactor;		//平衡因子
    TreeNode* left;
    TreeNode* right;
    TreeNode* parent;		//父节点指针
    TreeNode(int x) : val(x), left(nullptr), right(nullptr), parent(nullptr){}
};

2.如何创建一棵二叉搜索树

那么如何创建一棵二叉搜索树呢，我们肯定不能沿用普通二叉树的创建方法，普通二叉树都是按照一定的遍历顺序生成节点，而二叉搜索树根据插入元素的先后顺序则会形成不同的树。

我们最容易想到的就是 插入法 创建，首先将要插入的元素存储到vector容器中，然后遍历这个容器，容器的第一个元素作为树的根节点，继续遍历，如果元素比它大且右子树为空，则直接插入到它的右子树位置；若右子树不为空，则继续比较该元素与右子树节点的val大小，迭代下去。同理，如果元素比它小且左子树为空，则直接插入到它的左子树位置；若左子树不为空，则继续比较该元素与左子树节点val的大小。

推荐通过 迭代 进行创建，提高效率的同时便于理解整个过程。

代码如下：

/*
 * @param : 树根节点
 * @param : 插入元素
 */
TreeNode* InsertNode(TreeNode* root,int val){
    if(root==nullptr){			//插入的是第一个元素
        root=new TreeNode(val);
        return root;
    }
    TreeNode* temp=root;
    while(temp!=nullptr){
        if(val<=temp->val){		//如果插入元素小于等于根节点的val
            if(temp->left==nullptr){	//左子树为空树
                temp->left=new TreeNode(val);
                temp->left->parent=temp;	//注意父指针的指向要调整
                break;
            }
            temp=temp->left;	//向左子树迭代
        }
        if(val>temp->val){		//如果插入元素大于根节点的val
            if(temp->right==nullptr){	//右子树为空树
                temp->left=new TreeNode(val);
                temp->right->parent=temp;
                break;
            }
            temp=temp->right;	//向右子树迭代
        }
    }
    return root;
}

tip：注意我这里的函数返回的是指向树根的指针，如果你想用void的方式来书写插入函数，考虑到函数的拷贝传参问题，所以你传进去的形参必须是引用类型(TreeNode*& root)，当传入的是引用类型时，函数就会把原本的root指针传进去，否则的话传入的是root的拷贝，函数只是对这个拷贝指针的指向进行了改变，而root本身的指向并没有改变，所以会导致错误发生。

关于函数的拷贝传参，我举个简单的例子：

void myswap1(int x,int y){
	int temp=x;
	x=y;
	y=temp;
}
void myswap2(int& x,int& y){
	int temp=x;
	x=y;
	y=temp;
}
int main(){
	int x=1,y=9;
	myswap1(x,y);
	cout<<"第一次交换结果:x="<<x<<",y="<<y<<endl;
	myswap2(x,y);
	cout<<"第二次交换结果:x="<<x<<",y="<<y<<endl;
}

https://i-blog.csdnimg.cn/blog_migrate/00595ee2f9041120bad2a59eca5ff173.png

从运行结果中我们容易发现第一个交换函数并没有真正交换两个数的值，原因就是函数的拷贝传参，实际函数传入的是x，y的副本，x，y实际的值并没有改变；改用引用类型就可以把原本的x，y传入进去。

在主函数中我们应该这样书写：

int temp,n;
TreeNode* root=nullptr;
cout<<"请输入结点个数:";
cin>>n;
cout<<"请依此输入结点数值:";
for(i=0;i<n;i++){
	cin>>temp;
	nums.push_back(temp);
}
for(auto val : nums)
	root=InsertNode(root,val);

3.二叉搜索树的平衡化旋转

当vector中存放的元素依次为1，2，3，4，5，6，7这样的数据时，我们用上述方法创建的二叉搜索树是一棵链状的树，查找效率较低，因此需要做出调整使之平衡。

那么我们该如何进行“调整”呢？我们可以在每次插入新的节点前，遍历所有节点并更新它们的平衡因子，如果出现不平衡情况(平衡因子绝对值大于1)，就进行相应的调整。仔细想一想，不平衡的情况是在插入节点之后出现的，所以我们 从最新插入的节点向上遍历直至根节点 ，就可以找出所有的失衡点，而不需要去遍历其它的节点了。

这是更新所有节点平衡因子的函数：

//获得以结点x为根的二叉树高度(最大深度)
int GetDepth(TreeNode* x){
    if(x==nullptr)
        return 0;
    int left_height=GetDepth(x->left);
    int right_height=GetDepth(x->right);
    return max(left_height,right_height)+1;
}
//获得结点x的平衡因子
int GetBalanceFactor(TreeNode* x){
    int left=GetDepth(x->left);
    int right=GetDepth(x->right);
    return left-right;
}
//平衡因子更新，注意这里root不需要传引用，因为我们修改的是指针指向一块区域内部的值，没有修改指针指向
void UpdateBalanceFactor(TreeNode* root){
    if(root==nullptr)   return;
    root->BalanceFactor=GetBalanceFactor(root);
    UpdateBalanceFactor(root->left);
    UpdateBalanceFactor(root->right);
}

接下来就是最重要的旋转操作了，由于我们是自最近插入点开始向上遍历，所以要对插入函数进行小小的修改，只需把 最后一行改成return temp ，返回最新插入点的父节点，因为最新插入点的平衡因子一定是0，所以不用检查。对于所有的失衡点，我们可以分为四种不同的情况，进行旋转，分别为LL、RR、LR、RL。

这是最简单的LL型旋转：

https://i-blog.csdnimg.cn/blog_migrate/0ef7cbf5000ba080c1f22f9c2802d723.png

一般情况下，A,B,C都可能存在左右子树，假设在C的子树中插入一个节点后其高度变为h，则A失衡(在代码中我们将其设为x)。再旋转中，首先将B的右子树接到A的左子树位置处，然后B(代码中我们将其设为son)上升到A原来的位置，A下降为B的右子树，最后修改A(x)，B(son)父节点的指向。

https://i-blog.csdnimg.cn/blog_migrate/059677f34aff2028d7fcccc88134c46f.png

//LL型调整
TreeNode* LL_rotate(TreeNode* x){
    TreeNode* parent=x->parent;
    TreeNode* son=x->left;
    if(son->right!=nullptr)		//检查son节点是否存在右孩子
        son->right->parent=x;	//修改其父指针指向
    x->left=son->right;			//将son的右孩子接到x的左孩子位置上
    son->right=x;				//将x下降为son的右孩子位置
    son->parent=parent;			//修改son的父指针指向，指向原来x的父节点
    if(parent!=nullptr){		//如果失衡结点不是根结点
        if(parent->left==x)
            parent->left=son;
        else parent->right=son;
    }
    x->parent=son;				//修改x的父指针指向
    return son;					//返回原来x的位置(现被替换为son节点)
}

RR型旋转：(RR型基本上与LL型相同，只不过是一个镜像的操作)

//RR型调整
TreeNode* RR_rotate(TreeNode* x){
    TreeNode* parent=x->parent;
    TreeNode* son=x->right;
    if(son->left!=nullptr)
        son->left->parent=x;
    x->right=son->left;
    son->left=x;
    son->parent=parent;
    if(parent!=nullptr){
        if(parent->left==x)
            parent->left=son;
        else parent->right=son;
    }
    x->parent=son;
    return son;
}

LR型旋转：

对于一般情况下的LR型旋转，我们发现对B节点进行一次RR旋转，C的左子树接到了B的右子树位置，接着A,C,B就构成了LL的情况，所以在对失衡点A进行一次LL型旋转即可完成操作。

https://i-blog.csdnimg.cn/blog_migrate/5c38c12216cdd18b5ad58ae6d2c03cee.png

//LR型调整(x为离操作点最近的失衡点)
TreeNode* LR_rotate(TreeNode* x){
    RR_rotate(x->left);
    return LL_rotate(x);
}

RL型旋转：(同理这也是一个镜像的操作)

//RL型调整(x为离操作点最近的失衡点)
TreeNode* RL_rotate(TreeNode* x){
    LL_rotate(x->right);
    return RR_rotate(x);

最后我们需要一个调整函数，从最近的插入点开始，向上搜索，如果发现不平衡点则对该点进行旋转操作，注意上面的旋转操作 返回的都是原来相同位置上的节点 ，以便更新平衡因子后继续向上搜索，直至根节点。

调整函数如下：

//平衡二叉树调整
TreeNode* AVL_Adjustment(TreeNode* root,TreeNode* x){
    while(x!=nullptr){
        UpdateBalanceFactor(root);		//更新平衡因子
        if(x->BalanceFactor>1||x->BalanceFactor<-1){
            if(x->BalanceFactor>1){		//树左高右低
                if(x->left->BalanceFactor>0)
                    x=LL_rotate(x);
                else x=LR_rotate(x);
            }
            else{						//树右高左低
                if(x->right->BalanceFactor<0)
                    x=RR_rotate(x);
                else x=RL_rotate(x);
            }
            if(x->parent==nullptr){		//搜索到根节点时停止循环
                root=x;
                break;
            }
        }
        x=x->parent;					//一直向上迭代
    }
    return root;
}

最后直接调用创建函数就OK了

//创建平衡二叉树
TreeNode* CreateBBST(TreeNode* root,int val){
    TreeNode* temp=InsertNode(root,val);
    root=AVL_Adjustment(root,temp);		//每插入一个节点就进行一次调整
    return root;
}

4.直接创建平衡的二叉搜索树

看了上面的旋转过程，相信会有些朋友感到头晕了，他们会想：难道就没有更简单的方法去创建平衡二叉树吗？为什么非得转来转去的？答案是肯定的。当vector中的元素是有序的时候，我们可以直接选择按照一定的顺序去插入节点，直接就构成一棵平衡二叉树，从而绕过旋转的步骤。

首先，我们对vector中元素进行排序，选择中间元素作为树的根节点，然后总是选择中间元素左边区间的中间元素插入左子树，总是选择中间元素右边区间的中间元素插入右子树，递归，直至区间中只有一个元素。

代码如下：

TreeNode* midmake(vector<int>& nums,int left,int right){
	if(left>right)
		return nullptr;
	int mid=(left+right)/2;				//获取中间元素
	TreeNode* root=new TreeNode(nums[mid]);
	root->left=midmake(nums,left,mid-1);	//从左侧区间构造左子树
	root->right=midmake(nums,mid+1,right);	//从右侧区间构造右子树
	return root;
}
int main(){
	int temp,n;
	TreeNode* root=nullptr;
	cout<<"请输入结点个数:";
	cin>>n;
	cout<<"请依此输入结点数值:";
	for(i=0;i<n;i++){
		cin>>temp;
		nums.push_back(temp);
	}
	sort(nums.begin(),nums.end());
	root=midmake(nums,0,nums.size()-1);
}

好了，本篇文章到这里就结束了，希望所有看过这篇文章的朋友们都能够轻松的掌握平衡二叉搜索树，后续还会推出关于BST节点的插入，删除，查找等相关操作，尽请期待！

致力于将数据结构和算法讲透彻、讲清晰，欢迎大家关注。

更新于 2022-05-08
 算法, 数据结构, 指针, 二叉树, C
返回 | 主页