平衡二叉树

AVL简称平衡二叉树，缩写为BBST，由苏联数学家 Adelse-Velskil 和 Landis 在 1962 年提出。

二叉树是动态查找的典范，但在极限情况下，二叉树的查找效果等同于链表，而平衡二叉树可以完美的达到 $log_2 n$ 。

一直想深入的研究一下，并手写平衡二叉树的插入、删除代码。

可惜的是，国内数据结构的神级教材：阎蔚敏老师主编《数据结构》一书中并未看到关于AVL树的代码。

例子：

将17，9，2，12，14，26，33，15，40，23，25一次插入到一棵初始化为空的AVL树中，画出该二叉平衡树。

解：过程和结果如下图所示。

在这里插入图片描述

所谓平衡二叉树，就是指二叉树的左、右子树的深度差不超过2。每当插入一个新的元素，导致左右子树的深度超过2层时，需要对二叉树的失衡节点进行平衡，保持左右子树高度差在-1到1之间。

可以使用两个整数来表示左右子树的深度，前面一个表示左子树的层数，右边一个代表右子树的层数。

调整时，首先需要找到要平衡的节点。找到调整节点后，处理的方法有4种：

上图中圆标号1的是左-左结构，标号2的是左-右结构，标号3的是右-右，标号4的是右-左结构，这4种结构的处理方式各有不同。

左-左结构，即(2，1)结构

中间节点当作父节点，最上面的节点当作右节点，最下边节点当作左节点

左-右结构，即(2，-1)结构

最下面节点当作父节点，父节点当作右节点，中间节点当作左节点

右-右结构，即(-2，-1)结构

中间节点当作父节点，最上面的节点当作左节点，最下边节点当作右节点

右-左结构，即(-2，1)结构

最下面节点当作父节点，最上面节点当作左节点，中间节点当作右节点

编程中，计算左、右子树深度的代码如下：


int deep(BBST* b) {
	if (b == 0)
	{
		return 0;
	}

	int ld =  deep(b->lchild);
		
	int rd = deep(b->rchild) ;
	
	return ld > rd ? ld + 1 : rd + 1;
}

有了上面的理论和编程基础，我们可以慢慢的调试并手动写出平衡二叉树的插入代码：



int BBSTree::insert(ELEMENT* e) {
	if (mTree == 0)
	{
		mTree = newnode(e);
		mSize = 1;
		return 1;
	}

	BBST* t = mTree;

	BBST* tc = 0;
	Stack s;

	ELEMENT elem;

	while (1) {
		if (e->e == t->data.e) {
			return 0;
		}
		else if (e->e > t->data.e)
		{
			if (t->rchild == 0)
			{
				tc = newnode(e);
				tc->parent = t;
				t->rchild = tc;
				mSize++;
				break;
			}
			else {			
				elem.e = (unsigned long long)t;
				s.push((ELEMENT*)&elem);

				t = t->rchild;				
			}
		}
		else {
			if (t->lchild == 0)
			{
				tc = newnode(e);
				tc->parent = t;

				t->lchild = tc;
				mSize++;
				break;
			}
			else {
				elem.e = (unsigned long long)t;
				s.push((ELEMENT*)&elem);

				t = t->lchild;		
			}
		}
	}

	while (s.isEmpty() == 0) {

		s.pop(&elem);
		BBST* b = (BBST*)elem.e;
		b->ld = deep(b->lchild);
		b->rd = deep(b->rchild);

		t->ld = deep(t->lchild);
		t->rd = deep(t->rchild);

		int high_diff = b->ld - b->rd;
		int low_diff = t->ld - t->rd;
		if(high_diff == 2 && low_diff == 1)
		{
			BBST* f = (BBST*)b->parent;
			if (f&&f->lchild == b)
			{
				f->lchild = t;
			}
			else if (f&&f->rchild == b)
			{
				f->rchild = t;
			}
			t->parent = f;

			BBST* tr = t->rchild;
			t->rchild = b;
			b->parent = t;
		
			b->lchild = tr;
			if (tr)
			{
				tr->parent = b;
			}

			if (b == mTree)
			{
				mTree = t;
			}
		}
		else if (high_diff == 2 && low_diff == -1)
		{
			BBST* f = (BBST*)b->parent;
			if (f->lchild == b)
			{
				f->lchild = tc;
			}
			else if (f->rchild == b)
			{
				f->rchild = tc;
			}
			tc->parent = f;

			t->parent = tc;
			if (tc->lchild)
			{
				tc->lchild->parent = t;
			}
			
			t->rchild = tc->lchild;

			b->parent = tc;
			if (tc->rchild)
			{
				tc->rchild->parent = b;
			}
			
			b->lchild = tc->rchild;

			tc->rchild = b;
			tc->lchild = t;		

			if (b == mTree)
			{
				mTree = tc;
			}
		}
		else if (high_diff == -2 && low_diff == 1)
		{
			BBST* f = (BBST*)b->parent;
			if (f&&f->lchild == b)
			{
				f->lchild = tc;
			}
			else if (f&&f->rchild == b)
			{
				f->rchild = tc;
			}
			tc->parent = f;

			b->parent = tc;
			b->rchild = tc->lchild;
			if (tc->lchild)
			{
				tc->lchild->parent = b;
			}

			t->parent = tc;
			t->lchild = tc->rchild;
			if (tc->rchild)
			{
				tc->rchild->parent = t;
			}
			
			tc->rchild = t;
			tc->lchild = b;

			if (b == mTree)
			{
				mTree = tc;
			}
		}
		else if (high_diff == -2 && low_diff == -1)
		{
			BBST* f = (BBST*)b->parent;
			if (f && f->lchild == b)
			{
				f->lchild = t;
			}
			else if (f && f->rchild == b)
			{
				f->rchild = t;
			}
			t->parent = f;

			BBST* tl = t->lchild;
			t->lchild = b;
			b->parent = t;
		
			b->rchild = tl;
			if (tl)
			{
				tl->parent = b;
			}

			if (b == mTree)
			{
				mTree = t;
			}
		}
		tc = t;
		t = b;
	}

	return 0;
}