1. 简介文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 其中最为经典当属AVL树。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
总计而言就是：平衡二叉树是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
2. 性值文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
AVL树具有下列性质的二叉树（注意，空树也属于一种平衡二叉树）：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
l 它必须是一颗二叉查找树文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
l 它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
l 若将二叉树节点的平衡因子BF定义为该节点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有节点的平衡因子只可能为-1,0,1.文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
l 只要二叉树上有一个节点的平衡因子的绝对值大于1，那么这颗平衡二叉树就失去了平衡。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
3.实现:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
AVL树的构建我们需要明白一个核心的操作，整个实现过程是通过在一棵平衡二叉树中依次插入元素(按照二叉排序树的方式)，若出现不平衡，则要根据新插入的结点与最低不平衡结点的位置关系进行相应的调整。各个调整的方法分为LL型、RR型、LR型和RL型4种类型，其余的操作与一般的树进行插入和修改数据无异，这里由于篇幅关系不做过多缀数，以其中一种LR型调整为例说明，其余各种也都是举一反三思考：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
由于在A的左孩子(L)的右子树(R)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由1变为2。图5是LR型的最简单形式。显然，按照大小关系，结点C应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
①将B的左孩子C提升为新的根结点文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
②将原来的根结点A降为C的右孩子文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
③各子树按大小关系连接(BL和AR不变，CL和CR分别调整为B的右子树和A的左子树)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
4. 代码演示：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
代码仅作参考，具体实现请根据实际情况修改：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25219.html
#include<stdio.h>#include<stdlib.h> //结点设计 typedef struct Node { int key; struct Node *left; struct Node *right; int height;} BTNode; int height(struct Node *N) { if (N == NULL) return 0; return N->height;} int max(int a, int b) { return (a > b) ? a : b;} BTNode* newNode(int key) { struct Node* node = (BTNode*)malloc(sizeof(struct Node)); node->key = key; node->left = NULL; node->right = NULL; node->height = 1; return(node);} //ll型调整 BTNode* ll_rotate(BTNode* y) { BTNode *x = y->left; y->left = x->right; x->right = y; y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; return x;} //rr型调整 BTNode* rr_rotate(BTNode* y) { BTNode *x = y->right; y->right = x->left; x->left = y; y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; return x;} //判断平衡int getBalance(BTNode* N) { if (N == NULL) return 0; return height(N->left) - height(N->right);} //插入结点&数据BTNode* insert(BTNode* node, int key) { if (node == NULL) return newNode(key); if (key < node->key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); else return node; node->height = 1 + max(height(node->left), height(node->right)); int balance = getBalance(node); if (balance > 1 && key < node->left->key) //LL型 return ll_rotate(node); if (balance < -1 && key > node->right->key) //RR型 return rr_rotate(node); if (balance > 1 && key > node->left->key) { //LR型 node->left = rr_rotate(node->left); return ll_rotate(node); } if (balance < -1 && key < node->right->key) { //RL型 node->right = ll_rotate(node->right); return rr_rotate(node); } return node;} //遍历void preOrder(struct Node *root) { if (root != NULL) { printf("%d ", root->key); preOrder(root->left); preOrder(root->right); }} int main() { BTNode *root = NULL; root = insert(root, 2); root = insert(root, 1); root = insert(root, 0); root = insert(root, 3); root = insert(root, 4); root = insert(root, 4); root = insert(root, 5); root = insert(root, 6); root = insert(root, 9); root = insert(root, 8); root = insert(root, 7); printf("前序遍历："); preOrder(root); return 0;} |