数据结构（5）-- 图解AVL树（平衡二叉搜索树）

看、未来

发布于 2021-09-18 10:13:26

5130

发布于 2021-09-18 10:13:26

文章被收录于专栏：CSDN搜“看，未来”

文章目录

前言

之前种过AVL树，为什么要再写呢？依旧是因为我忘了，重刷一遍呗。

平衡二叉搜索树（AVL树）

二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序，例如序列A = {1，2，3，4，5，6}，构造二叉搜索树如图。依据此序列构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为O(n)。

如下图：

在此二叉搜索树中查找元素6需要查找6次。二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。同样的序列A，改为下图方式存储，查找元素6时只需比较3次，查找效率提升一倍。

可以看出当节点数目一定，保持树的左右两端保持平衡，树的查找效率最高。这种左右子树的高度相差不超过1的树为平衡二叉树。

AVL树的节点数据结构

和上面使用的那个普通结构略有不同。

class TreeNode{
public:
	//这几个数据放做公有的，方便操作
    int depth; //深度，这里计算每个结点的深度，通过深度的比较可得出是否平衡
    TreeNode* parent; //该结点的父节点，方便操作
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), depth(0), left(NULL), right(NULL) {}
    TreeNode() : val(0), depth(0), left(NULL), right(NULL) {}
};

在原始数据上创建AVL树

我的代码尝试：（先对原始数据进行排序，然后再填充二叉搜索树，使用递归的方式。）

#include<iostream>
#include<vector>
using namespace std;

void createTree(vector<int>& vec, TreeNode* root, int begin, int end) {
    //如果只剩一个键
    if (begin == end) {
        root->val = vec[begin];
        return;
    }

    int mid_sz = (begin+end)/2;
    root->val = vec[mid_sz];

    if (mid_sz - 1 >= begin) {
        root->left = new TreeNode(0);
        createTree(vec, root->left, begin, mid_sz - 1);
    }

    root->right = new TreeNode(0);
    createTree(vec, root->right,mid_sz + 1,end);
}

void PreOrderTraverse(TreeNode* root) {
    if (NULL == root)
        return;
    cout << root->val;
    PreOrderTraverse(root->left);
    PreOrderTraverse(root->right);
}

int main() {
    TreeNode* roott = new TreeNode(0);
    vector<int> vec = { 0,1,2,3,4,5,6,7};
    createTree(vec,roott,0,vec.size()-1);
    PreOrderTraverse(roott);
}

调整树的节点使平衡的操作：旋转

LL （右旋）：在左叶的左侧插入数据

图解过程：

代码实现：

//在左叶的左侧插入数据
TreeNode* LL(TreeNode* root) {
    TreeNode* x = root->left;	//即将返回的节点是y的左子节点（就是那个B）
    TreeNode* temp = x->right;	//先把y的右子节点取出来（就是那个E）
    x->right = root;			//把y放进x的右子节点（把A放到B的右节点）
    root->left = temp;			//把前面预存的放到y的左子节点（把E放到A的右节点）
    return x;					//(返回那个B)
}

int main() {
    TreeNode* roott = new TreeNode(0);
    vector<int> vec = { 0,1,2,3,4,5,6,7};
    createTree(vec,roott,0,vec.size()-1);
    roott = LL(roott);
    PreOrderTraverse(roott);
}

RR（左旋）：在右子叶的右侧插入数据

图解过程：

右旋其实就是上面左旋的镜像过程，所以不难，直接仿写上面左旋的过程即可：

代码实现

TreeNode* RR(TreeNode* root) {
    TreeNode* x = root->right;	//即将返回的节点是y的右子节点
    TreeNode* temp = x->left;	//先把x的左子节点取出来
    x->left = root;			//把y放进x的左子节点
    root->right = temp;			//把前面预存的放到y的右子节点  
    return x;
}

int main() {
    TreeNode* roott = new TreeNode(0);
    vector<int> vec = { 0,1,2,3,4,5,6,7};
    createTree(vec,roott,0,vec.size()-1);
    roott = RR(roott);
    PreOrderTraverse(roott);
}

后面的部分，就比较抽象了。

LR（左右旋）：在左叶节点的右侧插入数据

我们将这种情况抽象出来，得到下图：

我们需要对节点y进行平衡的维护。步骤如下图所示（第三个图里面x和z的位置换一下。）：

代码实现

TreeNode* LR(TreeNode* root) {
	root->left = RR(root->left);
	root = LL(root);
	return root;
}
//简单明了啊

RL（右左旋）：在右叶节点的左侧插入数据

我们将这种情况抽象出来，得到下图：

我们需要对节点y进行平衡的维护。步骤如下图所示（第三个图里面x和z的位置换一下。）：

第二个图中y的左孩子为T1 （被水印遮住的部分为：T1，T2，T3，T4）

代码实现

TreeNode* RL(TreeNode* root) {
    root->right = LL(root->right);
    root = RR(root);
    return root;
}
//简单明了啊

新节点的插入

在这里需要先补两个函数，虽然可能现在看不懂，但是配上调用函数的上下文就懂了。

计算平衡因子

int getBalanceFactor(TreeNode* node){
	if(node==NULL){
		return 0;
	}
	return get_depth(node->left)-getHeight(node->right);
}

int get_depth(TreeNode* node){
	if(node==NULL){
		return 0;
	}
	return node->depth;
}

对getBalanceFactor函数返回值的分析：

如果刚插入的叶子节点的爷爷节点的返回值大于0
1. 如果刚插入的叶子节点的父节点的返回值大于0：(LL)
2. 如果刚插入的叶子节点的父节点的返回值小于0：(LR)
如果刚插入的叶子节点的爷爷节点的返回值小于0
1. 如果刚插入的叶子节点的父节点的返回值大于0：(RL)
2. 如果刚插入的叶子节点的父节点的返回值小于0：(RR)

完整代码（测试过）

更新有点慢了，这两天事情太多，加上要调整两地状态。

#include<iostream>
#include<vector>

using namespace std;

class TreeNode {
public:
	//这几个数据放做公有的，方便操作
	int depth; //深度，这里计算每个结点的深度，通过深度的比较可得出是否平衡
	int val;
	TreeNode* left;
	TreeNode* right;

	TreeNode(int x) : val(x), depth(0), left(NULL), right(NULL) {}
	TreeNode() : val(0), depth(0), left(NULL), right(NULL) {}

	int getnode() {
		return this->val;
	}

	TreeNode* getleft() {
		return this->left;
	}

	TreeNode* getright() {
		return this->right;
	}

	void setleft(TreeNode* node) {
		this->left = node;
	}

	void setright(TreeNode* node) {
		this->right = node;
	}
};


void preorder(TreeNode* head) {
	if (head == NULL) {
		return;
	}
	cout << head->getnode() << endl;
	preorder(head->getleft());
	preorder(head->getright());
}


class AVL_Tree {
public:
	AVL_Tree() {

	}
	
	TreeNode* right_rotate(TreeNode* root) {
		TreeNode* temp = root->left;
		root->left = temp->right;
		temp->right = root;

		return temp;
	}

	TreeNode* left_rotate(TreeNode* root) {
		TreeNode* temp = root->right;
		root->right = temp->left;
		temp->left = root;

		return temp;
	}

	TreeNode* right_left_rotate(TreeNode* root) {
		root->right = right_rotate(root->right);
		return left_rotate(root);
	}

	TreeNode* left_right_rotate(TreeNode* root) {
		root->left = left_rotate(root->left);
		return right_rotate(root);
	}

	int get_depth(TreeNode* node) {

		if (!node) {
			return 0;
		}

		int maxL = 0;
		int maxR = 0;

		//2.计算左子树的最大深度； 
		if (node->left != NULL)
			maxL = get_depth(node->left);

		//3.计算右子树的最大深度； 
		if (node->right != NULL)
			maxR = get_depth(node->right);

		//4.当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1 
		return maxL > maxR ? maxL + 1 : maxR + 1; 
	}

	int getbalance(TreeNode* node) {
		return get_depth(node->left) - get_depth(node->right);
	}

	//先假设这个二叉树足够高
	TreeNode* insert_node(TreeNode* head,int val) {	//插入一个节点，不管三七二十一先插到叶子节点再说
		
		if (head != NULL) {
			if (val < head->val) {
				head->left = insert_node(head->left, val);
			}
			else {
				head->left = insert_node(head->right, val);
			}
		}
		else {	//这里不放else等着失败
			head = new TreeNode(val);
		}

		//插入之后就该旋转了
		if (getbalance(head) == 2) {	//如果需要旋转（左边高）
			if (getbalance(head->left) == 1) {	//左左，需要右右旋转
				return right_rotate(head);	//这里还需要向上衔接
			}
			else if (getbalance(head->left) == -1) {	//左右，这里需要右左旋转
				return right_left_rotate(head);
			}
		}
		else if (getbalance(head) == -2) {	//如果需要旋转（右边高）
			if (getbalance(head->right) == -1) {	//右右，需要左左旋转
				return left_rotate(head);	//这里还需要向上衔接
			}
			else if (getbalance(head->right) == -1){	//左右，这里需要右左旋转
				return left_right_rotate(head);
			}
		}

		return head;
	}

	TreeNode* delete_node(TreeNode* head,int val) {

		if (head!=NULL) {
			if (val < head->val) {
				head->left = delete_node(head->left, val);
			}
			else if(val > head->val){
				head->left = delete_node(head->right, val);
			}
			else {
				TreeNode* temp = head->left;
				while (temp && temp->right) {
					temp = temp->right;
				}
				head->val = temp->val;
				if (temp->left) {	//如果最右子节点还有左子节点
					//那顶多就一个节点
					temp->val = temp->left->val;
					//temp->left = temp->left->left;
					//temp->right = temp->left->right;
					temp->left->val = NULL;
					delete temp->left;
				}
				else {
					temp->val = NULL;
					delete temp;
				}
				return NULL;
			}
		}

		if (getbalance(head) == 2) {	//如果需要旋转（左边高）
			if (getbalance(head->left) == 1) {	//左左，需要右右旋转
				return right_rotate(head);	//这里还需要向上衔接
			}
			else if (getbalance(head->left) == -1) {	//左右，这里需要右左旋转
				return right_left_rotate(head);
			}
		}
		else if (getbalance(head) == -2) {	//如果需要旋转（右边高）
			if (getbalance(head->right) == -1) {	//右右，需要左左旋转
				return left_rotate(head);	//这里还需要向上衔接
			}
			else if (getbalance(head->right) == -1) {	//左右，这里需要右左旋转
				return left_right_rotate(head);
			}
		}
		return head;
	}
};

int main() {
	//TreeNode* a0 = new TreeNode(0);
	TreeNode* a1 = new TreeNode(1);
	//TreeNode* a2 = new TreeNode(2);
	TreeNode* a3 = new TreeNode(3);
	//TreeNode* a4 = new TreeNode(4);
	TreeNode* a5 = new TreeNode(5);
	TreeNode* a6 = new TreeNode(6);
	TreeNode* a7 = new TreeNode(7);
	//TreeNode* a8 = new TreeNode(8);
	TreeNode* a9 = new TreeNode(9);
	//TreeNode* a10 = new TreeNode(10);

	a5->setleft(a3);
	a5->setright(a7);

	a3->setleft(a1);
	//a3->setright(a4);

	a7->setleft(a6);
	a7->setright(a9);

	AVL_Tree* avl = new AVL_Tree();
	a5 = avl->insert_node(a5,2);	//左左插入
	preorder(a5);

	//cout << avl->get_depth(a5) << endl;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/02/07 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

二叉树

登录后参与评论

0 条评论

热度