[C++知识库]AVL树(c++)

?

#include <iostream>
#include <queue>

using namespace std;

class Node {
public:
	Node(Node *p, int target) {
		key = target;
		parent = p;
		height = 1;
		lchild = rchild = NULL;
	}
public:

	int key;
	Node *lchild;
	Node *rchild;
	Node *parent;
	int height;
};

class AVLTree
{
public:
	AVLTree() { m_root = NULL; }
	Node* connect34(Node *a, Node *b, Node *c, Node *T0, Node *T1, Node *T2, Node *T3);

	void insert(int target);
	bool isLChild(Node *p);
	bool isRChild(Node *p);
	bool isBalance(Node *node);
	void printAVLTree();
	void printNode(Node *p);
	void print_interval(int num, string s);
	void remove(int target);
	Node * removeAt(int target);
	Node* rotateAt(Node * v);
	Node* search(int target);
	void updateHeight(Node * p);
	void updateHeightAbove(Node * x);
	Node * tallerChild(Node *p);

private:
	Node * m_root;
};


Node * AVLTree::search(int target)
{
	if (m_root == NULL) {
		return NULL;
	}

	Node *p = m_root;
	while (p != NULL) {
		if (p->key == target) break;
		p = (target < p->key) ? p->lchild : p->rchild;
	}

	return p;
}


Node * AVLTree::tallerChild(Node *p)
{
	if (p == NULL) return NULL;

	int lHeight = (p->lchild == NULL) ? 0 : p->lchild->height + 1;
	int rHeight = (p->rchild == NULL) ? 0 : p->rchild->height + 1;

	return (lHeight > rHeight) ? p->lchild : p->rchild;
}

void AVLTree::insert(int target)
{
	if (m_root == NULL) {
		m_root = new Node(NULL, target);
		return;
	}

	if (search(target) != NULL) { // 已存在则不插入
		return;
	}

    // 1、插入
	Node *p = m_root;
	while (p != NULL) {
		if (target < p->key) {
			if (p->lchild != NULL) {
				p = p->lchild;
			}
			else {
				p->lchild = new Node(p, target);
				// 更新p的高度
				updateHeight(p);
				break;
			}
		}
		else {
			if (p->rchild != NULL) {
				p = p->rchild;
			}
			else {
				p->rchild = new Node(p, target);
				// 更新p的高度
				updateHeight(p);
				break;
			}
		}
	}
	
	// 从P开始向根节点处检查是否有失衡，有则重平衡，没有更新高度。另外插入只需要重平衡一次即可。
	while ((p->parent != NULL)) {
		if (!isBalance(p->parent)) {
			Node * v = tallerChild(p);
			Node *b = rotateAt(v); // 插入只需要重平衡一次即可恢复整个树的平衡

			while (b->parent != NULL) {
				b = b->parent;
			}
			m_root = b; // 更新树根节点
			break;
		}
		else {
			updateHeight(p);
		}
		p = p->parent;
	}
	updateHeight(p);

}

bool AVLTree::isLChild(Node *p) // 判断自己是左孩子还是右孩子
{
	if (p->parent == NULL) return false;

	return (p->parent->lchild == p) ? true: false;
}

bool AVLTree::isRChild(Node *p) // 判断自己是左孩子还是右孩子
{
	if (p->parent == NULL) return false;

	return (p->parent->rchild == p) ? true : false;
}

Node* AVLTree::rotateAt(Node * v)
{
	Node *p = v->parent;
	Node *g = p->parent; // 最先失衡的节点g
	Node *b;
	Node *gg = g->parent;

	bool Lchild = false;
	if (isLChild(g)) {
		Lchild = true;
	}
	bool Rchild = false;
	if (isRChild(g)) {
		Rchild = true;
	}

	if (isLChild(p)) {
		if (isLChild(v)) {
			b = connect34(v,p,g,v->lchild,v->rchild,p->rchild,g->rchild);
		}
		else {
			b = connect34(p,v,g,p->lchild,v->lchild,v->rchild,g->rchild);
		}
	}
	else {
		if (isRChild(v)) {
			b = connect34(g,p,v, g->lchild, p->lchild, v->lchild, v->rchild);
		}
		else {
			b = connect34(g, v, p, g->lchild, v->lchild, v->rchild, p->rchild);
		}
	}

	b->parent = gg; // 3+4重构后b的父节点
	if (Lchild) {
		gg->lchild = b;
	}
	if (Rchild) {
		gg->rchild = b;
	}
	return b; 
}

void AVLTree::updateHeight(Node * p)
{
	if (p == NULL) return;

	int lHeight = (p->lchild == NULL) ? 0 : p->lchild->height;
	int rHeight = (p->rchild == NULL) ? 0 : p->rchild->height;

	p->height = 1 + ((lHeight > rHeight) ? lHeight : rHeight);
}

Node * AVLTree::connect34(Node *a, Node *b, Node *c, Node *T0, Node *T1, Node *T2, Node *T3)
{
	a->lchild = T0;
	a->rchild = T1;
	c->lchild = T2;
	c->rchild = T3;
	b->lchild = a;
	b->rchild = c;

	a->parent = b;
	c->parent = b;

	if (T0) T0->parent = a;
	if (T1) T1->parent = a;
	if (T2) T2->parent = c;
	if (T3) T3->parent = c;

	updateHeight(a);
	updateHeight(c);
	updateHeight(b);

	return b;
}


void AVLTree::printAVLTree()
{
	if (m_root == NULL)
		return;

	Node * p;
	queue<Node *> que;
	que.push(m_root);
	int num = 1;
	while (!que.empty()) {
		p = que.front();
		que.pop();
		printNode(p);

		if (p->lchild) que.push(p->lchild);
		if (p->rchild) que.push(p->rchild);
		num--;
		if (num == 0) {
			cout << "\n";
			num = que.size();
		}
	}
	cout << "\n";
}

void AVLTree::print_interval(int num, string s)
{
	for (int i = 0; i < num; i++) {
		cout << s.c_str();
	}
}


void AVLTree::printNode(Node *p)
{
	cout << "[ " << "k:" << p->key << ", h:" << p->height << "]   ";
}


bool AVLTree::isBalance(Node *node)
{
	int lh = (node->lchild == NULL) ? 0 : node->lchild->height;
	int rh = (node->rchild == NULL) ? 0 : node->rchild->height;

	return (abs(lh - rh) <= 1) ? true : false;
}

void AVLTree::remove(int target)
{
	Node *x = removeAt(target);
	if (x == NULL)
		return;
	
	updateHeightAbove(x);

	Node *g = x;
	Node * tmp = NULL;
	while (g != NULL) {
		if (!isBalance(g)) {
		    // 确定 v,p,g
			Node *p = tallerChild(g);
			Node *v = tallerChild(p);
			g = rotateAt(v);
		}
		updateHeight(g);

		tmp = g;
		g = g->parent;
	} 

	m_root = tmp; // 更新树根节点
}

void AVLTree::updateHeightAbove(Node * x)
{
	while (x != NULL) {
		updateHeight(x);
		x = x->parent;
	}
}


Node * AVLTree::removeAt(int target)
{
	// 1、找到目标节点位置，若不存在则结束
// 2、否则找替代者，从根节点开始沿途找替代者，然后删除替代者，沿途返回根节点的过程判断是否失衡及重平衡并更新树的高度
	Node * x = search(target);
	if (x == NULL)
		return NULL;

	Node *g = NULL; // 被真正删除的节点的父亲

	if (x->lchild == NULL) { //右孩子接替x
		Node *p = g = x->parent;

		if (isLChild(x)) {
			p->lchild = x->rchild;
		}
		else if (isRChild(x)) {
			p->rchild = x->rchild;
		}

		if (x->rchild) {
			x->rchild->parent = p;
		}
		delete x;
	}
	else if (x->rchild == NULL) { // 左孩子接替x
		Node *p = g = x->parent;

		if (isLChild(x)) {
			p->lchild = x->lchild;
		}
		else if (isRChild(x)) {
			p->rchild = x->lchild;
		}
		x->lchild->parent = p;
		delete x;
	}
	else { // x的左子树的最大的k替换x,并删除k对应的节点，且修改x的父节点
		Node *xx = x->lchild;
		while (xx->rchild != NULL) {
			xx = xx->rchild;
		}

		// 1、修正x
		x->key = xx->key;

		// 2、处理替死鬼xx
		if (xx->lchild == NULL) {
			if (isLChild(xx)) {
				xx->parent->lchild = NULL;
			}
			if (isRChild(xx)) {
				xx->parent->rchild = NULL;
			}
		}
		else if (xx->lchild != NULL) {
			if (isLChild(xx)) {
				xx->parent->lchild = xx->lchild;
			}
			if (isRChild(xx)) {
				xx->parent->rchild = xx->lchild;
			}
			xx->lchild->parent = xx->parent;
		}
		g = xx->parent;
		delete xx;
	}

	return g;
}

int main()
{
	AVLTree avl;

	cout << "=============================测试插入===========================" << endl;
	int buf[] = { 3, 86, 45, 99, 77, 22, 56, 88, 32, 44, 46, 100, 78, 10 };
	
	//for (int i = 0; i < sizeof(buf) / sizeof(buf[0]); i++)

	int i = 0;
	cout << "\n" << "插入:" << buf[i] << endl;
	avl.insert(buf[i]);
	avl.printAVLTree();

	i = 1;
	cout << "\n" << "插入:" << buf[i] << endl;
	avl.insert(buf[i]);
	avl.printAVLTree();

	i = 2;
	cout << "\n" << "插入:" << buf[i] << endl;
	avl.insert(buf[i]);
	avl.printAVLTree();

	i = 3;
	cout << "\n" << "插入:" << buf[i] << endl;
	avl.insert(buf[i]);
	avl.printAVLTree();

	i = 4;
	cout << "\n" << "插入:" << buf[i] << endl;
	avl.insert(buf[i]);
	avl.printAVLTree();

	i = 5;
	cout << "\n" << "插入:" << buf[i] << endl;
	avl.insert(buf[i]);
	avl.printAVLTree();

	i = 6;
	cout << "\n" << "插入:" << buf[i] << endl;
	avl.insert(buf[i]);
	avl.printAVLTree();

	i = 7;
	cout << "\n" << "插入:" << buf[i] << endl;
	avl.insert(buf[i]);
	avl.printAVLTree();

	i = 8;
	cout << "\n" << "插入:" << buf[i] << endl;
	avl.insert(buf[i]);
	avl.printAVLTree();

	cout << "=============================测试删除===========================" << endl;

#if 0
	cout << "\n" << "删除:" << 56 << endl;
	avl.remove(56);
	avl.printAVLTree();


	cout << "\n" << "删除:" << 88 << endl;
	avl.remove(88);
	avl.printAVLTree();
#endif

	cout << "\n" << "删除:" << 32 << endl;
	avl.remove(32);
	avl.printAVLTree();

	cout << "\n" << "删除:" << 45 << endl;
	avl.remove(45);
	avl.printAVLTree();

#if 0
	for (int i = 0; i < 2; i++)
	{
		cout << "\n" << "插入:" << buf[i] << endl;
		avl.insert(buf[i]);
		avl.printAVLTree();
	}
#endif
	return 0;
}

?