浙大陈姥姥版数据结构：第四章二叉搜索树与平衡二叉树

### 二叉搜索树

#### 定义
二叉搜索树（BST），也称为二叉查找树或二叉排序树，是一种特殊的二叉树。其主要特性如下：
1. 左子树的所有节点值均小于根节点值。
2. 右子树的所有节点值均大于根节点值。
3. 左右子树本身也是二叉搜索树。

```c
struct TreeNode {
ElementType Data;
struct TreeNode *Left;
struct TreeNode *Right;
};
```

#### 查找操作
查找从根节点开始，若树为空则返回NULL。根据X与根节点键值的比较结果决定在左子树或右子树中继续查找，直到找到匹配节点或到达空节点。

递归实现：
```c
Position Find(ElementType X, BinTree BST) {
if (!BST) return NULL;
if (X > BST->Data) return Find(X, BST->Right);
else if (X Data) return Find(X, BST->Left);
else return BST;
}
```

迭代实现：
```c
Position IterFind(ElementType X, BinTree BST) {
while (BST) {
if (X > BST->Data) BST = BST->Right;
else if (X Data) BST = BST->Left;
else return BST;
}
return NULL;
}
```

#### 查找最大和最小元素
- 最小元素位于最左分支的端节点。
- 最大元素位于最右分支的端节点。

```c
Position FindMin(BinTree BST) {
if (!BST) return NULL;
while (BST->Left) BST = BST->Left;
return BST;
}

Position FindMax(BinTree BST) {
if (!BST) return NULL;
while (BST->Right) BST = BST->Right;
return BST;
}
```

#### 插入操作
插入操作通过类似查找的方法找到元素应插入的位置。

```c
BinTree Insert(ElementType X, BinTree BST) {
if (!BST) {
BST = malloc(sizeof(struct TreeNode));
BST->Data = X;
BST->Left = BST->Right = NULL;
} else if (X Data) BST->Left = Insert(X, BST->Left);
else if (X > BST->Data) BST->Right = Insert(X, BST->Right);
return BST;
}
```

#### 删除操作
删除操作分为三种情况：
1. 要删除的节点是叶节点。
2. 要删除的节点只有一个子树。
3. 要删除的节点有两个子树。

```c
BinTree Delete(ElementType X, BinTree BST) {
if (!BST) printf("not find");
else if (X Data) BST->Left = Delete(X, BST->Left);
else if (X > BST->Data) BST->Right = Delete(X, BST->Right);
else {
if (BST->Left && BST->Right) {
Position tmp = FindMin(BST->Right);
BST->Data = tmp->Data;
BST->Right = Delete(tmp->Data, BST->Right);
} else {
Position tmp = BST;
if (!BST->Left) BST = BST->Right;
else if (!BST->Right) BST = BST->Left;
free(tmp);
}
}
return BST;
}
```

### 平衡二叉树

#### 定义
平衡二叉树（AVL树）是指任意节点的左右子树高度差不超过1的二叉搜索树。其高度通常与斐波那契数列相关。

#### 平衡因子
平衡因子（Balance Factor, BF）定义为BF(T) = h_L - h_R，其中h_L和h_R分别是左右子树的高度。

#### 平衡调整
当插入或删除节点导致树不平衡时，需要进行旋转操作以恢复平衡。常见的旋转方式有：RR旋转、LL旋转、LR旋转和RL旋转。

### 判别是否为同一棵二叉搜索树

#### 方法
1. 分别构建两棵树并比较。
2. 不建树，直接通过序列判别。
3. 构建一棵树，再验证其他序列是否与该树一致。

```c
typedef struct TreeNode *Tree;
struct TreeNode {
int v; // 结点的基本信息
Tree Left, Right;
int flag; // 标记是否访问过
};
```

以上是关于二叉搜索树及平衡二叉树的详细介绍，希望对您有所帮助。