数据结构(7.3_2)——平衡二叉树
平衡二叉树，简称平衡树(AVL树)----树上任一结点的左子树和右子树的高度之差不超过1.
结点的平衡因子=左子树高-右子树高
//平衡二叉树结点
typedef struct AVLNode {
int key;//数据域
int blalance;//平衡因子
struct AVLNode* lchild, * rchild;
}AVLNode,*AVLTree;平衡二叉树的插入
在二叉排序树中插入新结点后，如何保持平衡？
调整最小不平衡子树
LL：
RR：
LR：
RL：
代码思路：
右旋转：
// 右旋转
Node *rightRotate(Node *y) {
Node *x = y->left;
Node *T2 = x->right;
// 执行旋转
x->right = y;
y->left = T2;
// 更新高度
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
// 返回新的根节点
return x;
}
左旋转：
// 左旋转
Node *leftRotate(Node *x) {
Node *y = x->right;
Node *T2 = y->left;
// 执行旋转
y->left = x;
x->right = T2;
// 更新高度
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
// 返回新的根节点
return y;
}
汇总：
填坑：
练习：
1、
2、
3、
查找效率分析
总结：
