平衡二叉树，简称平衡树(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、

查找效率分析 

总结：