二叉搜索树、平衡二叉树

－二叉搜索树

查找问题：静态查找和动态查找，静态查找可以用二分查找－判定树，那么针对动态查找数据如何组织？
（树的动态性强 比线性方便）
二叉搜索树（BST，Binary Search Tree）也称二叉排序树或二叉查找树
一棵二叉树满足以下性质：
1.非空左子树的所有键值小于其根结点的键值
2.非空右子树的所有键值大于其根结点的键值
3.左、右子树都是二叉搜索树

－二叉树的特殊函数：

二叉搜索树的查找操作（找出指定元素）：Find
Position Find ( ElementType X, BinTree BST )
{
if ( ! BST ) return NULL ; // 查找失败
if ( X > BST -> Data )
return Find ( X, BST -> Right ); // 在右子树中继续查找
Else if ( x < BST -> Data )
return Find ( x, BST -> Left ); // 在左子树中继续查找
else // X == BST -> Data
return BST; // 查找成功，返回找到结点的地址
}

上述算法运用到递归且都是尾递归，即在程序最后要返回时才递归，从编译角度看，尾递归可以用循环实现。
前文提到非递归函数执行效率更高，所以将“尾递归”函数改为迭代函数：
Position Find ( ElementType X, BinTree BST )
{
while ( BST ) {
if ( X > BST -> Data )
BST = BST -> Right; // 向右子树移动并查找
else if ( X < BST -> Data )
BST = BST -> Left; // 向左子树移动并查找
else // X == BST -> Data
return BST; // 查找成功，返回结点地址
}
return NULL; // 查找失败
}
查找效率决定于树的高度
查找最大值和最小值，即最左结点和最右结点

－二叉搜索树的插入

关键是找到元素应该插入的位置，可以采用与Find函数相似的方法，

BinTree Insert ( ElementType X, BinTree BST )
{
if ( ! BST ) {
// 若带插入的二叉搜索树为空树，则生成并返回只有一个结点的二叉搜索树；若带插入的二叉搜索树不为空树，则代表已经找到了应该插入的位置，就在该位置插入指定的元素
BST = malloc ( sizeof ( struct TreeNode ) );
BST -> Data = X;
BST -> Left = BST -> Right = NULL;
} else // 开始查找应该插入的位置
if ( X < BST -> Data )
BST -> Left = Insert ( X, BST -> Left ); // 递归插入左子树
Else if ( x > BST -> Data )
BST -> Right = Insert ( X, BST -> Right ); // 递归插入右子树
return BST; // else X已存在 什么都不用做
}

－二叉搜索树的删除

要考虑三种情况：
1.要删除的是叶结点：直接删除 并修改其父结点指针 值为NULL
2.要删除的结点只有一个子结点：将其父结点的指针指向要删除结点的孩子结点
3.最复杂的情况，要删除的结点有左右两棵子树，用另一结点替代被删除结点：右子树的最小元素或者左子树的最大元素，即将该情况转换为前面两种情况，右子树的最小元素或者左子树的最大元素必然是叶结点或者只有一个子结点的结点 要删除它们是比较方便的

BinTree Delete ( ElementType X, BinTree BST )
{
Position Tmp ;
if ( ! BST ) printf ( “要删除的元素未找到” ) ;
else if ( X < BST -> Data )
BST -> Left = Delete ( X, BST -> Left ); // 左子树递归删除
else if ( x > BST -> Data )
BST -> Right = Insert ( X, BST -> Right ); // 右子树递归删除
else // 找到要删除的结点，接下来判断该结点的子结点情况
if ( BST -> Left && BST -> Right ) { // 要被删除的结点有左右两个子结点
Tmp = FindMin ( BST -> Right ) ; // 在右子树中找最小的元素填充删除结点
BST -> Data = Tmp -> Data ;
BST -> Right = Delete ( BST -> Data, BST -> Right ) ; // 在删除结点的右子树中删除最小元素
} else { // 被删除结点有一个子结点或无子结点
Tmp = BST ;
if ( !BST -> Left ) // 有右孩子活着无子结点
BST = BST -> Right ;
else if ( ! BST -> Right ) ; // 有左孩子或无子结点
BST = BST -> Left ;
free ( Tmp ) ;
}
return BST ;
}

－平衡二叉树

搜索树结点不同插入次序，将导致不同的深度和平均查找长度ASL；平均查找长度ASL＝（层数＊该层结点数 的和）／总结点数
平衡因子（Balance Factor）：左子树的高度与右子树的高度的差
平衡二叉树（Balance Binary Tree）（AVL树）：空树，或者任一结点左右子树高度差的绝对值不超过1

－平衡二叉树的调整：

当我们往平衡二叉树中插入结点后，可能导致插入后的树不平衡，这时我们需要调整
右单旋：首先找出不平衡的“发现者”（左右子树高度差大于1的结点）“麻烦结点”（插入后导致不平衡的结点）在发现者右子树的右边，因而叫RR插入，需要RR旋转（右单旋）

002WV0d1zy70G7UnqgYec&690.png

上面例子中发现者是5， 麻烦结点是15
左单旋：类似的，左单旋即“麻烦结点”在“发现者”左子树的左边，因而叫LL插入，需要LL旋转（左单旋）

LR旋转：“麻烦结点”在“发现者”左子树的右边，因而叫LR插入，需要LR旋转

002WV0d1zy70G7WoqyN55&690.jpeg

RL旋转：“麻烦结点”在“发现者”右子树的左边，因而叫RL插入，需要RL旋转

002WV0d1zy70G7XVR2ce4&690.jpeg