【数据结构】二叉排序树和平衡二叉树

1. 二叉搜索树（BST）

1.1 二叉搜索树的定义及特点

1.1.1 定义

1.1.2 特点

1.2 二叉排序树的构造（创建）

1.2.1 基本思想

1.2.2 算法

1.3 二叉排序树的删除

2. 平衡二叉树（AVL）

2.1 为什么要用AVL

2.2 平衡二叉树相关概念

2.2.1 定义

2.2.2 平衡因子（Balance Factor）

2.2.3 最小不平衡子树

2.3 AVL树的构造和调整过程

2.3.1 基本原则

2.3.2 插入过程中的调整原则

2.3.3 两种旋转

2.3.4 四种情况

2.3.5 平衡二叉树的查找

3.代码实现

1. 二叉搜索树（BST）

1.1 二叉搜索树的定义及特点

1.1.1 定义

[二叉搜索树 Binary Sort Tree，BST] 二叉树中，任何结点均满足条件：“ 大于其左子树上的所有结点，小于其右子树上的所有结点（若存在的话）”。又称为二叉查找树（ Binary Search Tree ），或二叉排序树。

1.1.2 特点

（ 1 ）可以实现类似折半思想的查找，有较高的查找性能

（ 2 ）中序遍历二叉排序树，可得到一个有序序列！

1.2 二叉排序树的构造（创建）

1.2.1 基本思想

只要将数据元素链到合适的位置（满足性质）。

开始二叉树为空，然后重复在二叉树中插入元素，即：

读入数据元素

（1）若二叉树为空，则插入到空二叉树中，即该数据元素就是根；显然是二叉排序树。

（2）若二叉树不是空，则与根比较，若比根大则在右子树中插入，否则在左子树中插入。

1.2.2 算法

// 插入节点（BST）
PtrToTreeNode InsertBST(TreeNode *root, int data) {if(root == nullptr) {root = new TreeNode;root->data = data;root->left = root->right = nullptr;} else {if(data < root->data) {root->left = InsertBST(root->left, data);} else if(data > root->data) {root->right = InsertBST(root->right, data);}}return root;
}

1.3 二叉排序树的删除

二叉排序树的删除操作比其他操作更为复杂，有三种情况需要考虑；

（1）要删除的是叶节点——可以直接删除，然后再修改其父节点的指针。

（2）要删除的节点只有一个孩子节点——删除需要改变其父节点的指针，指向要删除节点的孩子节点。

（3）要删除的节点有左、右两棵子树——为了保持二叉搜索树的有序性，替代被删除的元素位置可以有两种选择：一种是取其右子树中的最小元素；另一个是取其左子树中的最大元素。

2. 平衡二叉树（AVL）

2.1 为什么要用AVL

动态查找表本身是在查找过程中动态生成的，即对于给定值key，若查找表中存在其关键码等于key的元素，则查找成功返回，否则插入关键码等于key的元素。

动态查找表可以是线性表，也可以是树（二叉排序树）。最常用的动态查找表是：二叉排序树。

查找方法：

        若二叉排序树为空，则查找不成功，在二叉排序树中插入该元素；否则:

        ① 若给定值等于根结点的关键字，则查找成功；

        ② 若给定值小于根结点的关键字，则继续在左子树上进行查找；

        ③ 若给定值大于根结点的关键字，则继续在右子树上进行查找。

特点：查找效率与构造的二叉排序树的深度有关；

对于每一颗特定的二叉排序树，均可按照平均查找长度的定义来求它的ASL值：

$ASL=\sum_{i=1}^{n} p_{i}\times c_{i}$

其中： $p_{i}$ 是查找第 i 个元素的概率，通常假设为等概率。

$c_{i}$ 是查找第 i 个元素的比较次数，这里 $c_{i}=h_{i}$

显然，由n个关键字构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。

例如：

        由关键字序列 [1，2，3，4，5] 构造而得的二叉排序树：

                ASL =（1+2+3+4+5）/ 5 = 3

        由关键字序列 [3，1，2，5，4] 构造而得的二叉排序树：

                 ASL =（1+2+3+2+3）/ 5 = 2.2

所有这些二叉排序树中，最高n，最低 $log_{2}n$ 。

如何构造一棵查找效率高的二叉排序树？

2.2 平衡二叉树相关概念

2.2.1 定义

一棵二叉排序树是平衡的，当且仅当每个结点的左右子树的高度至多相差为1 。由G.M.Adelson-Velskii 和 E.M.Landis给出的定义—— AVL树。

递归定义：

（１）空树是二叉排序树（平衡二叉树）；

（２）它的左右子树都是平衡二叉树（左右子树的高度最多相差为１）；

2.2.2 平衡因子（Balance Factor）

左子树的高度－右子树的高度，即 $BF=H_{left}-H_{right}$

平衡二叉树中，对任意结点：BF = 1、0、-1，即 BF的绝对值小于等于1，如果大于1，平衡二叉树就失衡，需要旋转纠正。

2.2.3 最小不平衡子树

距离插入节点最近的，并且 BF 的绝对值大于 1 的节点为根节点的子树。

旋转纠正只需要纠正最小不平衡子树！

2.3 AVL树的构造和调整过程

2.3.1 基本原则

按照二叉排序树的构造方法，构造过程中判断是否为平衡二叉树（平衡因子），是，则继续构造；否则，按一定的原则（保持是二叉排序树和平衡）将其调整为平衡二叉树，然后继续。

2.3.2 插入过程中的调整原则

二叉排序树在插入前平衡，插入一个结点后如果失去平衡，则至少有一个结点的平衡因子变为＋２或－２。

若平衡因子＝＋２，则左分支高于右分支；

若平衡因子＝－２，则右分支高于左分支；

2.3.3 两种旋转

左旋
旧根节点为新根节点的左子树
新根节点的左子树（如果存在）为旧根节点的右子树
右旋：
旧根节点为新根节点的右子树
新根节点的右子树（如果存在）为旧根节点的左子树

2.3.4 四种情况

LL型：在左分支的左子树上插入一个结点后，失去平衡，BF=2

右旋

LR型：在左分支的右上子树插入一个结点后，失去平衡，BF=2

先左旋，再右旋

RR型：在右分支的右子树上插入一个结点后，失去平衡，BF=-2

左旋

RL型：在右分支的左子树上插入一个结点后，失去平衡，BF=-2

先右旋，再左旋

2.3.5 平衡二叉树的查找

1. 查找过程：同静态二叉排序树一样！

２. 效率分析： 查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。假设深度为 h 的二叉平衡树中所含结点数的最小值为 $N_{h}$ ，则显然 $N_{h}=N_{h-1}+N_{h-2}+1$

由此可以推导出： $h\approx log_{2}n$

因此，在平衡树上进行查找的时间复杂度为 $O(log_{2}(n))$

3.代码实现

// 二叉树结点定义
typedef struct TreeNode{int data;struct TreeNode *left;struct TreeNode *right;int height;
} TreeNode, *PtrToTreeNode;// 插入节点（BST）
PtrToTreeNode InsertBST(TreeNode *root, int data) {if(root == nullptr) {root = new TreeNode;root->data = data;root->left = root->right = nullptr;} else {if(data < root->data) {root->left = InsertBST(root->left, data);} else if(data > root->data) {root->right = InsertBST(root->right, data);}}return root;
}// 计算树的高度
int Height(TreeNode *root) {if(root == nullptr) {return -1;} else {return max(Height(root->left), Height(root->right)) + 1;}
}// 获取平衡因子
int GetBalance(TreeNode *root) {return root ? Height(root->left) - Height(root->right) : 0;
}// 左旋
TreeNode *LeftRotate(TreeNode *root) {TreeNode *newRoot = root->right; // 新根节点root->right = newRoot->left; // 新根的左子树newRoot->left = root; // 新根的左子树指向原根节点root->height = max(Height(root->left), Height(root->right)) + 1;newRoot->height = max(Height(newRoot->left), Height(newRoot->right)) + 1;return newRoot;
}// 右旋
TreeNode *RightRotate(TreeNode *root) {TreeNode *newRoot = root->left; // 新根节点root->left = newRoot->right; // 新根的右子树newRoot->right = root; // 新根的右子树指向原根节点root->height = max(Height(root->left), Height(root->right)) + 1;newRoot->height = max(Height(newRoot->left), Height(newRoot->right)) + 1;return newRoot;
}// 插入节点（AVL）
TreeNode *InsertAVL(TreeNode *root, int data) {if(root == nullptr) {root = new TreeNode;root->data = data;root->left = root->right = nullptr;return root;} else {if(data < root->data) {root->left = InsertAVL(root->left, data);} else if(data > root->data) {root->right = InsertAVL(root->right, data);}}root->height = max(Height(root->left), Height(root->right)) + 1;int balance = GetBalance(root);// 左子树高度大于右子树高度if(balance > 1) {// LL型if(Height(root->left->left) > Height(root->left->right)) {root = RightRotate(root);} else { //LR型root->left = LeftRotate(root->left);root = RightRotate(root);}} else if(balance < -1) { // 右子树高度大于左子树高度// RR型if(Height(root->right->right) > Height(root->right->left)) {root = LeftRotate(root);} else { // RL型root->right = RightRotate(root->right);root = LeftRotate(root);}}return root;
}// 计算查找长度
int SearchLength(TreeNode *root, int depth) {if(root == nullptr) {return 0;} else {return depth + SearchLength(root->left, depth + 1) + SearchLength(root->right, depth + 1);}
}