AVL平衡树

2023-11-02 16:52:22

跨考软工，学习数据结构，树。

### node节点是三叉链表

struct treeNode {
	int value;
	treeNode *parent;
	treeNode *lchild, *rchild;
	bool visited;
	int balance;//平衡因子，左-右，取值-1,0,1；
	treeNode()
		: value(0), lchild(nullptr), rchild(nullptr), parent(nullptr), visited(0), balance(0) {};
	treeNode(int val):
		value(val), lchild(nullptr), rchild(nullptr), parent(nullptr), visited(0), balance(0) {};
};

### 几种遍历方式

void visitTreeNode(treeNode *&root) {
	cout << root->value << "||" ;
	root->visited = 1;
	return ;
}

//前序遍历
void preorder(treeNode *&root) {
	if (root == nullptr)
		return;
	if (root->visited == 1)
		return;
	visitTreeNode(root);
	preorder(root->lchild );
	preorder(root->rchild );
	return;
}

//中序遍历
void midorder(treeNode *&root) {
	if (root == nullptr)
		return;
	if (root->visited == 1)
		return;
	midorder(root->lchild );
	visitTreeNode(root);
	midorder(root->rchild );
	return;
}

//后序遍历
void postorder(treeNode *&root) {
	if (root == nullptr)
		return;
	if (root->visited == 1)
		return;
	postorder(root->lchild );
	postorder(root->rchild );
	visitTreeNode(root);
	return;
}

//层序遍历
void bfsTree(treeNode *&root) {//此处的queue为辅助队列，可以用vector或者treeNode*[]替代
	queue<treeNode *> temp;
	temp.push(root);

	while (!temp.empty()) {
		treeNode *t = temp.front();
		if (t->lchild != nullptr)
			temp.push(t->lchild );
		if (t->rchild != nullptr)
			temp.push(t->rchild );
		visitTreeNode(t);
		temp.pop();
	}
	return;
}

### 左旋 右旋 左右旋 右左旋

///右旋函数
///parents:进行旋转的根节点
void turnR(treeNode *&parents) {
	if (parents == nullptr)
		return;
	if (parents->lchild == nullptr && parents->rchild == nullptr)
		return;
	treeNode *p = parents;
	treeNode *l = p->lchild ;
	treeNode *lr = l->rchild ;
	treeNode *pp = p->parent ;


	if (pp != nullptr)
		pp->lchild == p ? pp->lchild = l : pp->rchild = l;
	l->parent = pp;

	if (lr != nullptr)
		lr->parent = p;
	p->lchild = lr;

	p->parent = l;
	l->rchild = p;

	parents = l;//这一步赋值失败，直接跳过去了
	return;
}


///左旋函数
///parents:进行旋转的根节点
void turnL(treeNode *&parents) {
	if (parents == nullptr)
		return;
	if (parents->lchild == nullptr && parents->rchild == nullptr)
		return;
	treeNode *p = parents;
	treeNode *r = p->rchild ;
	treeNode *rl = r->lchild ;
	treeNode *pp = p->parent ;


	if (pp != nullptr)
		pp->lchild == p ? pp->lchild = r : pp->rchild = r;
	r->parent = pp;

	if (rl != nullptr)
		rl->parent = p;
	p->rchild = rl;

	p->parent = r;
	r->lchild = p;

	parents = r;
	return ;
}

//左右旋函数
void turnLR(treeNode *&root) {
	turnL(root->lchild );
	turnR(root);
}

//右左旋函数
void turnRL (treeNode *&root) {
	turnR(root->rchild );
	turnL(root);
}

### 插入删除调平函数以及两个辅助函数

int getTreeHeight(treeNode *root) {
	if (root == nullptr)
		return 0;
	return max(getTreeHeight(root->lchild ), getTreeHeight(root->rchild )) + 1;//当前树高度=左右子树高的那个+1
}

int getTreeBalance(treeNode *&root) {
	if (root == nullptr)
		return 0;
	return getTreeHeight(root->lchild ) - getTreeHeight(root->rchild );
}

//每次插入删除后调用
void takeBalanceTree(treeNode *&root) {
	if (root == nullptr)
		return ;
	root->balance = getTreeBalance(root);
	//右子树高
	if (root->balance < -1) {
		if (getTreeBalance(root->lchild ) > 1 || getTreeBalance(root->lchild ) < -1
		        || getTreeBalance(root->rchild ) > 1 || getTreeBalance(root->rchild ) < -1)
			else  //当前节点为最小不平衡树
				getTreeBalance(root->rchild ) == 1 ? turnRL(root) : turnL(root); //只会是1或者-1，（如果是0的话就不会造成不平衡）
	}
	//左子树高
	if (root->balance > 1) {
		if (getTreeBalance(root->lchild ) > 1 || getTreeBalance(root->lchild ) < -1
		        || getTreeBalance(root->rchild ) > 1 || getTreeBalance(root->rchild ) < -1)
			takeBalanceTree(root->rchild );
		else //当前节点为最小不平衡树
			getTreeBalance(root->lchild ) == -1 ? turnLR(root) : turnR(root);
	}
	//如果一棵平衡树插入一个值以后，根节点是平衡的，那么这棵树是平衡的。
	return;
}


//平衡树插入函数
void insert(treeNode *&root, int val) {
	if (root == nullptr) {
		root = new treeNode(val);
		return;
	}

	if (val > root->value && root->rchild != nullptr ) {
		insert(root->rchild, val);
		takeBalanceTree(root);
		return;
	}
	if (val > root->value && root->rchild == nullptr ) {
		root->rchild = new treeNode(val);
		root->rchild->parent = root;
		return;
	}
	if (val < root->value && root->lchild != nullptr ) {
		insert(root->lchild, val);
		takeBalanceTree(root);
		return;
	}
	if (val < root->value && root->lchild == nullptr ) {
		root->lchild = new treeNode(val);
		root->lchild->parent = root;
		return;
	}
}
treeNode *Delete(treeNode *&root, int data) {
	treeNode *parent = NULL;
	treeNode *now = root;
	while (now->value != data) {
		parent = now;
		if (now->value > data)
			now = now->lchild;
		else
			now = now->rchild;
	}

	if (now->lchild == NULL && now->rchild == NULL) { //叶子结点
		if (parent->lchild == now)
			parent->lchild = NULL;
		else
			parent->rchild = NULL;
		takeBalanceTree(root);
		return root;
	} else if (now->lchild == NULL && now->rchild != NULL) { //只有右孩子
		if (parent->lchild == now)
			parent->lchild = now->rchild;
		else
			parent->rchild = now->rchild;
		takeBalanceTree(root);
		return root;
	} else if (now->lchild != NULL && now->rchild == NULL) { //只有左孩子
		if (parent->lchild == now)
			parent->lchild = now->lchild;
		else
			parent->rchild = now->lchild;
		takeBalanceTree(root);
		return root;
	} else { //有双子
		treeNode *n = now->rchild;
		if (n ->lchild == NULL) {
			n->lchild = now->lchild ;
			if (parent->lchild == now)
				parent->lchild = n;
			else
				parent->rchild = n;
			takeBalanceTree(root);
			return root;
		}
	}
	return root;
}

主函数调用

int main() {
//	freopen("tree_in.txt", "r", stdin);
//	freopen("tree_out.txt", "w", stdout);
	int t;
	scanf("%d", &t);
	treeNode *root = new treeNode(t);
	while (scanf("%d", &t) != EOF) {
		if (t == -1)
			break;
		//cout << t << " ";
		insert(root, t);
		//	cout << endl;
	}
	midorder(root);

	return 0;
}

全家福

//刚开始写的时候是想写二叉树的，后来写着写着写成了平衡二叉查找树
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;



struct treeNode {
	int value;
	treeNode *parent;
	treeNode *lchild, *rchild;
	bool visited;
	int balance;//平衡因子，左-右，取值-1,0,1；
	treeNode()
		: value(0), lchild(nullptr), rchild(nullptr), parent(nullptr), visited(0), balance(0) {};
	treeNode(int val):
		value(val), lchild(nullptr), rchild(nullptr), parent(nullptr), visited(0), balance(0) {};
};

void visitTreeNode(treeNode *&root) {
	cout << root->value << "||" ;
	root->visited = 1;
	return ;
}

//前序遍历
void preorder(treeNode *&root) {
	if (root == nullptr)
		return;
	if (root->visited == 1)
		return;
	visitTreeNode(root);
	preorder(root->lchild );
	preorder(root->rchild );
	return;
}

//中序遍历
void midorder(treeNode *&root) {
	if (root == nullptr)
		return;
	if (root->visited == 1)
		return;
	midorder(root->lchild );
	visitTreeNode(root);
	midorder(root->rchild );
	return;
}

//后序遍历
void postorder(treeNode *&root) {
	if (root == nullptr)
		return;
	if (root->visited == 1)
		return;
	postorder(root->lchild );
	postorder(root->rchild );
	visitTreeNode(root);
	return;
}

//层序遍历
void bfsTree(treeNode *&root) {//此处的queue为辅助队列，可以用vector或者treeNode*[]替代
	queue<treeNode *> temp;
	temp.push(root);

	while (!temp.empty()) {
		treeNode *t = temp.front();
		if (t->lchild != nullptr)
			temp.push(t->lchild );
		if (t->rchild != nullptr)
			temp.push(t->rchild );
		visitTreeNode(t);
		temp.pop();
	}
	return;
}


///右旋函数
///parents:进行旋转的根节点
void turnR(treeNode *&parents) {
	if (parents == nullptr)
		return;
	if (parents->lchild == nullptr && parents->rchild == nullptr)
		return;
	treeNode *p = parents;
	treeNode *l = p->lchild ;
	treeNode *lr = l->rchild ;
	treeNode *pp = p->parent ;


	if (pp != nullptr)
		pp->lchild == p ? pp->lchild = l : pp->rchild = l;
	l->parent = pp;

	if (lr != nullptr)
		lr->parent = p;
	p->lchild = lr;

	p->parent = l;
	l->rchild = p;

	parents = l;//这一步赋值失败，直接跳过去了
	return;
}


///左旋函数
///parents:进行旋转的根节点
void turnL(treeNode *&parents) {
	if (parents == nullptr)
		return;
	if (parents->lchild == nullptr && parents->rchild == nullptr)
		return;
	treeNode *p = parents;
	treeNode *r = p->rchild ;
	treeNode *rl = r->lchild ;
	treeNode *pp = p->parent ;


	if (pp != nullptr)
		pp->lchild == p ? pp->lchild = r : pp->rchild = r;
	r->parent = pp;

	if (rl != nullptr)
		rl->parent = p;
	p->rchild = rl;

	p->parent = r;
	r->lchild = p;

	parents = r;
	return ;
}

//左右旋函数
void turnLR(treeNode *&root) {
	turnL(root->lchild );
	turnR(root);
}

//右左旋函数
void turnRL (treeNode *&root) {
	turnR(root->rchild );
	turnL(root);
}

int getTreeHeight(treeNode *root) {
	if (root == nullptr)
		return 0;
	return max(getTreeHeight(root->lchild ), getTreeHeight(root->rchild )) + 1;//当前树高度=左右子树高的那个+1
}

int getTreeBalance(treeNode *&root) {
	if (root == nullptr)
		return 0;
	return getTreeHeight(root->lchild ) - getTreeHeight(root->rchild );
}

//每次插入删除后调用
void takeBalanceTree(treeNode *&root) {
	if (root == nullptr)
		return ;
	root->balance = getTreeBalance(root);
	//右子树高
	if (root->balance < -1) {
		if (getTreeBalance(root->lchild ) > 1 || getTreeBalance(root->lchild ) < -1
		        || getTreeBalance(root->rchild ) > 1 || getTreeBalance(root->rchild ) < -1)
			else  //当前节点为最小不平衡树
				getTreeBalance(root->rchild ) == 1 ? turnRL(root) : turnL(root); //只会是1或者-1，（如果是0的话就不会造成不平衡）
	}
	//左子树高
	if (root->balance > 1) {
		if (getTreeBalance(root->lchild ) > 1 || getTreeBalance(root->lchild ) < -1
		        || getTreeBalance(root->rchild ) > 1 || getTreeBalance(root->rchild ) < -1)
			takeBalanceTree(root->rchild );
		else //当前节点为最小不平衡树
			getTreeBalance(root->lchild ) == -1 ? turnLR(root) : turnR(root);
	}
	//如果一棵平衡树插入一个值以后，根节点是平衡的，那么这棵树是平衡的。
	return;
}


//平衡树插入函数
void insert(treeNode *&root, int val) {
	if (root == nullptr) {
		root = new treeNode(val);
		return;
	}

	if (val > root->value && root->rchild != nullptr ) {
		insert(root->rchild, val);
		takeBalanceTree(root);
		return;
	}
	if (val > root->value && root->rchild == nullptr ) {
		root->rchild = new treeNode(val);
		root->rchild->parent = root;
		return;
	}
	if (val < root->value && root->lchild != nullptr ) {
		insert(root->lchild, val);
		takeBalanceTree(root);
		return;
	}
	if (val < root->value && root->lchild == nullptr ) {
		root->lchild = new treeNode(val);
		root->lchild->parent = root;
		return;
	}
}

treeNode *Delete(treeNode *&root, int data) {
	treeNode *parent = NULL;
	treeNode *now = root;
	while (now->value != data) {
		parent = now;
		if (now->value > data)
			now = now->lchild;
		else
			now = now->rchild;
	}

	if (now->lchild == NULL && now->rchild == NULL) { //叶子结点
		if (parent->lchild == now)
			parent->lchild = NULL;
		else
			parent->rchild = NULL;
		takeBalanceTree(root);
		return root;
	} else if (now->lchild == NULL && now->rchild != NULL) { //只有右孩子
		if (parent->lchild == now)
			parent->lchild = now->rchild;
		else
			parent->rchild = now->rchild;
		takeBalanceTree(root);
		return root;
	} else if (now->lchild != NULL && now->rchild == NULL) { //只有左孩子
		if (parent->lchild == now)
			parent->lchild = now->lchild;
		else
			parent->rchild = now->lchild;
		takeBalanceTree(root);
		return root;
	} else { //有双子
		treeNode *n = now->rchild;
		if (n ->lchild == NULL) {
			n->lchild = now->lchild ;
			if (parent->lchild == now)
				parent->lchild = n;
			else
				parent->rchild = n;
			takeBalanceTree(root);
			return root;
		}
	}
	return root;
}

int main() {
//	freopen("tree_in.txt", "r", stdin);
//	freopen("tree_out.txt", "w", stdout);
	int t;
	scanf("%d", &t);
	treeNode *root = new treeNode(t);
	while (scanf("%d", &t) != EOF) {
		if (t == -1)
			break;
		//cout << t << " ";
		insert(root, t);
		//	cout << endl;
	}
	midorder(root);

	return 0;
}

上一篇：题解 AVL 树


下一篇：数据结构与算法-基础（十一）AVL 树