本文主要是介绍从二叉排序树到平衡二叉树再到红黑树系列2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
上篇博客主要讲述了二叉排序树的基本概念和插入删除操作，必须再次说明的是：在一棵高度为h的二叉排序树上，实现动态集合操作查询,插入和删除的运行时间均为O(h)。
可见二叉树的基本操作效率取决于树的形态，当然树的高度越低越好，显然树分布越均匀，高度越低。那么，问题来了？对于给定的关键字序列，如何构造一棵形态匀称的二叉排序树。这种匀称的二叉排序树就称为平衡二叉树。
平衡二叉树定义：平衡二叉树或为空树，或其上任意一个节点，节点的左右子树高度差不超过1. 通常将二叉树上所有结点的左右子树的高度之差称为平衡因子。
构造平衡二叉树的常用算法有AVL树和红黑树等。其中，AVL树保持平衡的机制是靠平衡因子和旋转，而红黑树保持平衡的机制是靠 节点颜色约束和旋转，事实上，红黑树并不追求完全平衡，只能算部分平衡：没有路径能多余其他路径2倍长，但红黑树能以O(log2 n)的时间复杂度进行查询删除插入操作。 本篇博客先介绍AVL，下篇博客再讲解红黑树。
构造AVL树的基本思想：每当插入一个新结点时，首先检查是否因插入而破坏了树的平衡性；在保持二叉排序树的特性同时，(也就是说平衡二叉树得首先保证它是二叉排序树)调整最小不平衡子树各结点之间的指向，以达到新的平衡。<所谓最小不平衡子树就是指离插入点最近，且平衡因子大于1的结点作为根的子树，简而言之：就是从新插入结点位置开始向根节点寻找，第一个由平衡变为不平衡的结点>
typedef struct AVLTreeNode{Type key; // 关键字(键值)int height;struct AVLTreeNode *left; // 左孩子struct AVLTreeNode *right; // 右孩子
}Node, *AVLTree;与二叉排序树相比，平衡二叉树插入节点后还要保证插入后既要保证有序，又要保证平衡。那么保证的方法就是：旋转
插入新节点N导致平衡二叉树不再平衡，最小不平衡子树的根为A，插入位置不同，插入后调整节点平衡因子和指向也不同。可以归纳为如下4种情况（如图所示）：
注：图中节点用圈表示，子树用长方形表示，代表不止一个结点，可能一个，可能多个节点，长方形长度代表子树高度。红色标记为指针指向变化示意。
1> LL，新插入节点在A左孩子的左子树上：右旋，如图所示，当新添加节点N时，节点A的平衡因子bf（blancefactor）由1变为2，为了书写清晰直观描述为：A.bs = 1-->2(以下格式同) 而B.bs = 0--->1。为了保持平衡，这时需要节点A需要绕B向右旋转。
形象点说，就是指节点A本来就已经快要不平衡了（bs=1，左子树比右子树高），这个时候其左子树又添加一个结点，这不是压死骆驼的最后一根稻草么。。。这个时候就需要让树往右边旋转，降低节点A的高度。而节点B 添加N之前 bs=0，表示还有承受能力，这个时候给它加加担子，让他由小兵变将军，升到根节点去，这样树就变为平衡了。废话有点多，但是好理解。具体调整过程见代码。
static Node* left_left_rotation(AVLTree A)
{AVLTree B;B = A->left;A->left = B->right;B->right = A;A->height = MAX( HEIGHT(A->left), HEIGHT(A->right)) + 1;B->height = MAX( HEIGHT(B->left), A->height) + 1;return B;
}2>RR，新插入节点在A右孩子的右子树上：左旋；如图所示。和右旋原理类似，本来右子树就高，再来一节点，不得不左旋。
//左旋转处理函数
static Node* right_right_rotation(AVLTree A)
{AVLTree B;B = A->right;A->right = B->left;B->left = A;A->height = MAX( HEIGHT(A->left), HEIGHT(A->right)) + 1;B->height = MAX( HEIGHT(B->right), A->height) + 1;return B;
}3> LR，新插入节点在A左子树的右子树上，先左旋再右旋，准确点说是在A左子树的右子树的（左子树或右子上）
相比于操作1>和操作2>,操作3>相对复杂。这样操作的原因在于：插入新的节点N之前，根节点A和其左子树根节点B都是平衡因子不为0的节点：也就是说A.bf=1 B.bf=-1;
即他们与不平衡只差一步之遥了，再添加一个节点，且都是添加在他们的A的左子树，B的右子树的左子树下，他们要被压死了，这个时候，根节点A对子节点B说，你来当根节点。B一看，我的不平衡因子也不是0，没法当啊；于是，B左旋，把C顶上去。对A说，我不能当根节点，但是C可以，于是，再一次绕C右旋转，A下来，C当上了根节点。
，为什么C能当根节点？因为添加前C的平衡因子为0，即使添加一个节点后，它与不平衡依然还有一步之遥。
具体过程见代码
static Node* right_left_rotation(AVLTree A)
{A->left = right_right_rotation(A->left);return left_left_rotation(A);
}4>RL,新插入节点在A右子树的左子树上，先右旋再左旋。过程和LR是类似的，不再赘述。
直接贴代码
//插入操作时右平衡旋转处理函数
static Node* right_left_rotation(AVLTree A)
{A->right = left_left_rotation(A->right);return right_right_rotation(A);
}关于上述4种旋转的说明：4中操作的命名可以理解为插入节点的位置，如LL旋转，插入的节点在最小不平衡子树的左节点的左子树上，但是为了平衡要右旋。
旋转之前，首先要寻找最小不平衡子树的根，再判断需要4种旋转中哪一种旋转。最小不平衡子树旋转后新的根为：LL--->最小不平衡子树根的左子树
RR--->最小不平衡子树根的右子树 LR-->最小不平衡子树根的左子树的右节点 RL--->最小不平衡子树根的右子树的左节点。
插入操作如下：
/* * 将结点插入到AVL树中，并返回根节点** 参数说明：* tree AVL树的根结点* key 插入的结点的键值* 返回值：* 根节点*/
Node* avltree_insert(AVLTree tree, Type key)
{if (tree == NULL) {// 新建节点tree = avltree_create_node(key, NULL, NULL);if (tree==NULL){printf("ERROR: create avltree node failed!\n");return NULL;}}else if (key < tree->key) // 应该将key插入到"tree的左子树"的情况{tree->left = avltree_insert(tree->left, key);// 插入节点后，若AVL树失去平衡，则进行相应的调节。if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2){if (key < tree->left->key)tree = left_left_rotation(tree);elsetree = left_right_rotation(tree);}}else if (key > tree->key) // 应该将key插入到"tree的右子树"的情况{tree->right = avltree_insert(tree->right, key);// 插入节点后，若AVL树失去平衡，则进行相应的调节。if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2){if (key > tree->right->key)tree = right_right_rotation(tree);elsetree = right_left_rotation(tree);}}else //key == tree->key){printf("添加失败：不允许添加相同的节点！\n");}tree->height = MAX( HEIGHT(tree->left), HEIGHT(tree->right)) + 1;return tree;
}这篇关于从二叉排序树到平衡二叉树再到红黑树系列2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
