AVL树的插入与输出

概念引用：https://www.cnblogs.com/zhuwbox/p/3636783.html

AVL树：

　　AVL树本质上是一颗二叉查找树，但是它又具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为平衡二叉树。下面是平衡二叉树和非平衡二叉树对比的例图：

　　平衡因子(bf)：结点的左子树的深度减去右子树的深度，那么显然-1<=bf<=1;

AVL树的作用：

　　我们知道，对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度（O(log2n)）同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。

　　例如：我们按顺序将一组数据1,2,3,4,5,6分别插入到一颗空二叉查找树和AVL树中，插入的结果如下图：

　　　　　　　　

 

 

 

 

 

 

 

　　由上图可知，同样的结点，由于插入方式不同导致树的高度也有所不同。特别是在带插入结点个数很多且正序的情况下，会导致二叉树的高度是O(N)，而AVL树就不会出现这种情况，树的高度始终是O(lgN).高度越小，对树的一些基本操作的时间复杂度就会越小。这也就是我们引入AVL树的原因

AVL树的基本操作：

　　AVL树的操作基本和二叉查找树一样，这里我们关注的是两个变化很大的操作：插入和删除！

　　我们知道，AVL树不仅是一颗二叉查找树，它还有其他的性质。如果我们按照一般的二叉查找树的插入方式可能会破坏AVL树的平衡性。同理，在删除的时候也有可能会破坏树的平衡性，所以我们要做一些特殊的处理，包括：单旋转和双旋转！

　　AVL树的插入，单旋转的第一种情况---右旋：

　　由上图可知：在插入之前树是一颗AVL树，而插入之后结点T的左右子树高度差的绝对值不再 < 1,此时AVL树的平衡性被破坏，我们要对其进行旋转。由上图可知我们是在结点T的左结点的左子树上做了插入元素的操作，我们称这种情况为左左情况，我们应该进行右旋转(只需旋转一次，故是单旋转)。具体旋转步骤是：

　　T向右旋转成为L的右结点，同时，Y放到T的左孩子上。这样即可得到一颗新的AVL树，旋转过程图如下：

 

　　左左情况的右旋举例：

　　AVL树的插入，单旋转的第一种情况---左旋：

　
 

　　　由上图可知：在插入之前树是一颗AVL树，而插入之后结点T的左右子树高度差的绝对值不再 < 1,此时AVL树的平衡性被破坏，我们要对其进行旋转。由上图可知我们是在结点T的右结点的右子树上做了插入元素的操作，我们称这种情况为右右情况，我们应该进行左旋转(只需旋转一次，故事单旋转)。具体旋转步骤是：

　　　T向右旋转成为R的左结点，同时，Y放到T的左孩子上。这样即可得到一颗新的AVL树，旋转过程图如下：

　

　　右右情况的左旋举例：

　　以上就是插入操作时的单旋转情况！我们要注意的是：谁是T谁是L，谁是R还有谁是X,Y,Z!T始终是开始不平衡的左右子树的根节点。显然L是T的左结点，R是T的右节点。X、Y、Y是子树当然也可以为NULL.NULL归NULL，但不能破坏插入时我上面所说的左左情况或者右右情况。

　　AVL树的插入，双旋转的第一种情况---左右(先左后右)旋：

 

由　　上图可知，我们在T结点的左结点的右子树上插入一个元素时，会使得根为T的树的左右子树高度差的绝对值不再 < 1，如果只是进行简单的右旋，得到的树仍然是不平衡的。我们应该按照如下图所示进行二次旋转：

　　

　　左右情况的左右旋转实例：

　　AVL树的插入，双旋转的第二种情况---右左(先右后左)旋：

　　由上图可知，我们在T结点的右结点的左子树上插入一个元素时，会使得根为T的树的左右子树高度差的绝对值不再 < 1，如果只是进行简单的左旋，得到的树仍然是不平衡的。我们应该按照如下图所示进行二次旋转：

　　右左情况的右左旋转实例：

 C++代码实现：

#include <iostream>

struct AVLNode {
	int value;
	int height;
	AVLNode *left;
	AVLNode *right;
};

// 计算节点的高度
int Height(AVLNode *node) {
	if (node == 0)
		return 0;
	else
		return node->height;
}

int Max(int a, int b) {
	return a > b ? a : b;
}

// 单方向的左旋操作
AVLNode * SingleTrunLeft(AVLNode *node) {
	AVLNode *cache = node->right;
	node->right = cache->left;
	cache->left = node;
	node->height = Max(Height(node->left), Height(node->right)) + 1;
	cache->height = Max(Height(cache->left), Height(cache->right)) + 1;
	return cache;
}

// 单方向的右旋操作
AVLNode * SingleTrunRight(AVLNode *node) {
	AVLNode *cache = node->left;
	node->left = cache->right;
	cache->right = node;
	node->height = Max(Height(node->left), Height(node->right)) + 1;
	cache->height = Max(Height(cache->left), Height(cache->right)) + 1;
	return cache;
}

// 双方向先左旋再右旋操作
AVLNode * DoubleTrunLeftRight(AVLNode *node) {
	node->left = SingleTrunLeft(node->left);
	return SingleTrunRight(node);
}

// 双方向的先右旋再左旋操作
AVLNode * DoubleTrunRightLeft(AVLNode *node) {
	node->right = SingleTrunRight(node->right);
	return SingleTrunLeft(node);
}

AVLNode * InsertToTree(int v, AVLNode * node) {
	// 如果node为空，直接赋值
	if (node == 0)
	{
		node = new AVLNode();
		node->value = v;
		node->left = 0;
		node->right = 0;
		node->height = 0;
	}
	else if (v < node->value) {	// 往左边插入时，需判断插入的是node的左节点的左边还是右边来控制单方向还是双方向
		// 先插入到叶子节点上
		node->left = InsertToTree(v, node->left);
		// 如果插入之后不平衡再去判断插左节点的左边了还是右边了，如果插左边导致不平衡直接单方向左旋就可以了，如果是右边需要先左旋后右旋
		if (Height(node->left) - Height(node->right) >= 2) {
			if (v < node->left->value) {
				node = SingleTrunRight(node);
			}
			else {
				node = DoubleTrunLeftRight(node);
			}
		}
	}
	else if (v > node->value){
		node->right = InsertToTree(v, node->right);
		if (Height(node->right) - Height(node->left) >= 2) {
			if (v > node->right->value) {
				node = SingleTrunLeft(node);
			}
			else {
				node = DoubleTrunRightLeft(node);
			}
		}
	}
	node->height = Max(Height(node->left), Height(node->right)) + 1;
	return node;
}

// 输出的时候假定根节点是最靠右边的，因为是中序遍历所以输出左节点之前先左进一个tab，
// 到输出根节点的时候右进一个tab，输出右节点时需要再左进一个tab，最后需要再右进一个tab用来给外层的递归使用。
void PrintAVLTree(AVLNode * tree, int &tabCount) {
	if (tree == 0) return;
	tabCount--;
	PrintAVLTree(tree->left, tabCount);
	tabCount++;
	for (int i = 0; i < tabCount; i++) {
		std::cout << '\t';
	}
	std::cout << tree->value << std::endl;
	tabCount--;
	PrintAVLTree(tree->right, tabCount);
	tabCount++;
}

int main()
{
	AVLNode *tree = 0;

	tree = InsertToTree(1, tree);
	tree = InsertToTree(290, tree);
	tree = InsertToTree(3, tree);
	tree = InsertToTree(42, tree);
	tree = InsertToTree(5, tree);
	tree = InsertToTree(61, tree);
	tree = InsertToTree(7, tree);
	tree = InsertToTree(8, tree);
	tree = InsertToTree(91, tree);
	tree = InsertToTree(10, tree);
	tree = InsertToTree(111, tree);
	tree = InsertToTree(125, tree);
	tree = InsertToTree(13, tree);
	tree = InsertToTree(82, tree);
	tree = InsertToTree(32, tree);
	tree = InsertToTree(1666, tree);
	tree = InsertToTree(17, tree);
	int tabCount = Height(tree);
	PrintAVLTree(tree, tabCount);
	system("Pause");
	return 0;
}