数据结构（C语言描述）学习笔记、学习文档.zip

## 什么是平衡二叉树？ 平衡二叉树(Balanced Binary Tree)，由前苏联数学家[G. M. Adelson-Velsky](https://zh.wikipedia.org/wiki/格奥尔吉·阿杰尔松-韦利斯基)和[Evgenii Landis](https://zh.wikipedia.org/w/index.php?title=Evgenii_Landis&action=edit&redlink=1)在他们1962年的论文《An algorithm for the organization of information》中提出，因此也叫AVL树。 它是具有如下性质的树： 1. 可以是一棵空树 2. 可以是一颗左子树和右子树都是平衡二叉树且左右子树的深度之差的绝对值不超过1。 ## 简单理解平衡二叉树 上文也出现了递归定义，可以不严谨的理解为：要么是一棵空树，要么是一棵平衡二叉树，在这棵树中，以任意节点为根作为一棵新树，那么这棵新树也得是二叉平衡树。 二叉平衡树是对二叉搜索树的改进，为什么要改进二叉搜索树？ 假如有一棵二叉搜索树(BST)，且为一棵空树。 当我们插入一组升序数据[1, 3, 5, 7, 9]，BST1是这样的：  <center>（图1）</center> 当我们插入一组降序数据[10, 8, 6, 4, 2]，BST2是这样的：  <center>（图2）</center> 那么请问这两棵树是二叉搜索树吗？的确是，完全符合二叉搜索树的性质。但毫无疑问，看上去更像是个链表。确实，当插入一组有序数据时，二叉搜索树退化成了链表，此时的查找效率退化为O(N)。 ## 平衡因子 平衡因子(Balance Factor, BF)是某个节点左子树和右子树的高度之差（有的说法也叫深度之差，都是表达一个意思），一棵平衡二叉树的所有节点的平衡因子都只可能是0、-1、1。这一点也可以用来验证一棵二叉树是否为平衡二叉树。因为只要某二叉树的某个节点平衡因子大于1，那么该二叉树就一定不会是平衡二叉树。 如下由一棵平衡二叉树：  <center>（图3）</center> 其中H表示高度(height)，L表示左子树高度(Left height)，R表示右子树高度(Right height), BF是平衡因子(Balance Factor, BF=L-R)。 如下有一棵非二叉平衡树：  <center>（图4）</center> 其中根节点的平衡因子绝对值大于1，出现了“失衡”。 ## 从非平衡二叉树到平衡二叉树 如何创建一棵平衡二叉树呢？由于平衡二叉树是对二叉搜索树的改进，所以在做插入操作的时候，我们仍然按照二叉搜索树的方式：找到要插入的位置并进行插入。然后如果该树中出现了平衡因子绝对值大于1的节点，就说明该调整了。我们把离插入节点最近且平衡因子绝对值大于1的祖先节点，以该节点为根的子树称为**最小不平衡子树**。首先要调整的就是这棵子树。 假如我们要插入一组数据[2, 1, 0] 相继插入，2和1后，树是这样的：  <center>（图5）</center> 此时，并没有出现不平衡的情况，可以看作是一棵平衡二叉树。 但是插入0之后，就是图4那样了，根节点的平衡因子为2。我们以根节点2为根节点的树叫做**最小不平衡子树**，情况特殊，因为此时根节点出现了失衡，所以最小不平衡子树是它本身。 如下图的一棵非二叉平衡树，  <center>（图6）</center> 可以看到，在插入节点53之后，节点24和节点37的BF绝对值都大于1，但我们把以节点37为根的树叫做**最小不平衡子树**，因为它离刚插入的节点53最近。 ## 平衡二叉树与其节点的表示 ```c /* 平衡二叉树的节点 */ typedef struct avl_node { /* 关键字 */ int key; /* 左右节点指针 */ struct avl_node *left; struct avl_node *right; /* 节点的高度 */ int height; }avl_node; /* 平衡树二叉树本身 */ typedef struct avl { /* 指向二叉树根节点 */ struct avl_node *root; /* 树的节点数 */ int size; }avl; ``` ## 平衡二叉树及其节点的创建 ```c /* 创建一个节点 */ avl_node *avl_create_node(int key) { avl_node *node = (struct avl_node*)malloc(sizeof(struct avl_node)); if(node==NULL) return NULL; node->height = 1; node->key = key; node->left = NULL; node->right = NULL; return node; } /* 创建一棵平衡二叉树 */ avl *avl_create(void) { avl *avl = (struct avl*)malloc(sizeof(struct avl)); if(avl==NULL) return NULL; avl->root = NULL; avl->size = 0; return avl; } ``` ## 节点的高度相关函数 ```c /* 返回一个节点的高度 */ int avl_height(avl_node *node) { if(node==NULL) return 0; return node->height; } /* 比较一个key和一个节点的key的大小 * 如果key比较大，返回真，否则返回假。 */ int avl_compare_key(int key, avl_node *node) { if(node==NULL) return 0; if(key > node->key) return 1; return 0; } /* 返回两个节点中的高度较大值 */ int max(avl_node *x, avl_node *y) { int m = avl_height(x); int n = avl_height(y); return m>=n?m:n; } ``` ### 四种不平衡情况 一棵平衡二叉树在插入某个节点后失衡，只会出现四种不平衡类型。在每种不平衡类型中在处理不平衡的操作中，顺时针旋转，叫做右旋；逆时针旋转叫做左旋。 ### LL型 LL型可以看作是重心在Left，需要进行一次右旋操作。 ```c /* LL型，需要向右旋 */ avl_node *avl_rotate_ll(avl_node *node) { /* 新的“根” */ avl_node *top = node->left; node->left = top->right; top->right = node; /* 重新计算高度, 注意：node与top的高度计算次序千万不能颠倒 */ node->height = max(node->left, node->right) + 1; top->height = max(top->left, top->right) + 1; return top; } ``` 下图演示了最小不平衡子树是它本身（简称情况1）： 找到最小不平衡子树（根节点31）后右旋。我们把最小不平衡子树的左子树作为新的top节点。  下图演示了最小不平衡子树的根不是二叉树的根，也即最小不平衡子树是二叉树的“真子树”（情况2）。类似于集合中的真子集。  ### RR型 ```c /* RR型，需要向左旋 */ avl_node *avl_rotate_rr(avl_node *node) { avl_node *top = node->right; node->right = top->left; top->left = node; /* 重新计算高度 */ node->height = max(node->left, node->right) + 1; top->height = max(top->left, top->right) + 1; return top; } ``` 情况1：  情况2：  ### LR型 假如对空树AVL插入一组数据[31, 25, 28] 相继插入31，25后没问题，接着插入28:  此时出现了以节点31为根节点的不平衡子树，既不是LL型，也不是RR型，而是LR型。需要进行两次操作，第一次对根节点的左子�