本文共 5154 字,大约阅读时间需要 17 分钟。
平衡二叉树一般指平衡树。平衡树(Balance Tree,BT) 指的是,任意节点的子树的高度差都小于等于1。常见的符合平衡树的有B树(多路平衡搜索树)、AVL树(二叉平衡搜索树)等。平衡树可以完成集合的一系列操作,时间复杂度和空间复杂度相对于“2-3树”要低,在完成集合的一系列操作中始终保持平衡,为大型数据库的组织、索引提供了一条新的途径。
例: 搜索树结点不同插入次序,将导致不同的深度和平均查找长度ASL。
平衡二叉树(Balanced Binary Tree) (AVL树): ⋆ \star ⋆ 空树;
⋆ \star ⋆ 或者任一结点左、右子树高度差的绝对值不超过1,即 ∣ B F ( T ) ∣ ⩽ 1 |BF(T)|\leqslant1 ∣BF(T)∣⩽1。平衡二叉树的高度能达到 l o g 2 n log_{2}n log2n吗? l o g 2 n log_{2}n log2n是结点为 n n n的完全二叉树的高度。
假设有下图左边所示的平衡二叉树,当在其右子树的右边插入元素Nov时二叉树变为如下图中间所示的情况,由于根结点Mar的平衡因子变为-2,所以二叉树不平衡了,需要进行调整。调整的关键是使得元素Mar、May、Nov处于平衡状态,采用RR旋转,得到下图右边所示的平衡二叉树。
AVLTree RRRotation(AVLTree A){ // 此时根节点是A AVLTree B = A->right; // B为A的右子树 A->right = B->left; // B的左子树挂在A的右子树上 B->left = A; // A挂在B的左子树上 return B; // 此时B为根结点 }
假设有下图左边所示的平衡二叉树,当在其左子树的左边插入元素Apr时二叉树变为如下图中间所示的情况,由于左孩子结点Mar的平衡因子变为2,所以二叉树不平衡了,需要进行调整。调整的关键是使得元素Mar、Aug、Apr处于平衡状态,采用LL旋转,得到下图右边所示的平衡二叉树。
AVLTree LLRotation(AVLTree A){ // 此时根节点是A AVLTree B = A->left; // B为A的左子树 A->left = B->right; // B的右子树挂在A的左子树上 B->right = A; // A挂在B的右子树上 return B; // 此时B为根结点 }
假设有下图左边所示的平衡二叉树,当在其左子树的右边插入元素Jan时二叉树变为如下图中间所示的情况,由于根结点May的平衡因子变为2,所以二叉树不平衡了,需要进行调整。调整的关键是使得元素May、Aug、Mar处于平衡状态,采用LR旋转,得到下图右边所示的平衡二叉树。
AVLTree LRRotation(AVLTree A){ // 先RR旋转 A->left = RRRotation(A->left); // 再LL旋转 return LLRotation(A);}
假设有下图左边所示的平衡二叉树,当在其左子树结点的右边孩子节点的左边插入元素Feb时二叉树变为如下图中间所示的情况,由于左孩子结点Aug的平衡因子变为-2,所以二叉树不平衡了,需要进行调整。调整的关键是使得元素Aug、Jan、Dec处于平衡状态,采用RL旋转,得到下图右边所示的平衡二叉树。
AVLTree RLRotation(AVLTree A){ // 先LL旋转 A->right = LLRotation(A->right); // 再RR旋转 return RRRotation(A); }
综合调整的实例如下图所示。
AVL树是一种自平衡二叉搜索树,在AVL树中任何结点的两个子树的高度最多相差1。假设由于在二叉搜索树上插入结点而失去平衡,则需要进行调整以恢复此属性,如下图所示。
#includeusing namespace std;typedef struct AVLNode *AVLTree;struct AVLNode { int data; // 存值 AVLTree left; // 左子树 AVLTree right; // 右子树 int height; // 树高 };// 返回最大值 int Max(int a, int b) { return a > b ? a : b;}// 返回树高,空树返回-1 int getHeight(AVLTree A) { return A == NULL ? -1 : A->height;}// LL旋转// 把B的右子树腾出来挂给A的左子树,再将A挂到B的右子树上去 AVLTree LLRotation(AVLTree A) { // 此时根节点是A AVLTree B = A->left; // B为A的左子树 A->left = B->right; // B的右子树挂在 A 的左子树上 B->right = A; // A 挂在B的右子树上 A->height = Max(getHeight(A->left), getHeight(A->right)) + 1; B->height = Max(getHeight(B->left), A->height) + 1; return B; // 此时B为根结点 }// RR旋转AVLTree RRRotation(AVLTree A) { // 此时根节点是A AVLTree B = A->right; A->right = B->left; B->left = A; A->height = Max(getHeight(A->left), getHeight(A->right)) + 1; B->height = Max(getHeight(B->left), A->height) + 1; return B; // 此时B为根结点 }// LR旋转 AVLTree LRRotation(AVLTree A) { // 先RR旋转 A->left = RRRotation(A->left); // 再LL旋转 return LLRotation(A);}// RL旋转AVLTree RLRotation(AVLTree A) { // 先 LL 单旋 A->right = LLRotation(A->right); // 再 RR 单旋 return RRRotation(A);}AVLTree Insert(AVLTree T, int x) { if (!T) // 如果该结点为空,初始化结点 { T = (AVLTree)malloc(sizeof(struct AVLNode)); T->data = x; T->left = NULL; T->right = NULL; T->height = 0; } else // 否则不为空 { if (x < T->data) // 左子树 { T->left = Insert(T->left, x); if (getHeight(T->left) - getHeight(T->right) == 2) // 如果左子树和右子树高度差为 2 { if (x < T->left->data) // LL旋转 T = LLRotation(T); else if (x > T->left->data) // LR旋转 T = LRRotation(T); } } else if (x > T->data) // 右子树 { T->right = Insert(T->right, x); if (getHeight(T->right) - getHeight(T->left) == 2) { if (x < T->right->data) // RL旋转 T = RLRotation(T); else if (x > T->right->data) // RR旋转 T = RRRotation(T); } } } //更新树高 T->height = Max(getHeight(T->left), getHeight(T->right)) + 1; return T;}int main() { AVLTree T = NULL; int n; cin >> n; for (int i = 0; i < n; i++) { int tmp; cin >> tmp; T = Insert(T, tmp); } cout << T->data << endl; system("pause"); return 0;}
运行上述代码,进行测试。
588 70 61 96 120
代码运行的测试效果如下图所示,AVL树的根结点为70(对应图1)所示的树)。
788 70 61 96 120 90 65
代码运行的测试效果如下图所示,AVL树的根结点为88(对应图4)所示的树)。
转载地址:http://wxaez.baihongyu.com/