浙大数据结构第四周之04-树6 Complete Binary Search Tree

**浙大数据结构第四周之04-树6 Complete Binary Search Tree**

在前面的几周中，我们已经学习了二叉树的基本概念、遍历算法以及各种类型的二叉树。今天，我们要讨论的是一种特殊的二叉树——完全二叉搜索树（Complete Binary Search Tree，简称CBST）。

**什么是完全二叉搜索树？**

完全二叉搜索树是一种特殊的二叉搜索树，它满足以下条件：

1. 每个结点都有一个键值。
2. 每个结点的左子树和右子树都是完全二叉搜索树。
3. 每个结点的左子树中所有结点的键值都小于该结点的键值。
4. 每个结点的右子树中所有结点的键值都大于该结点的键值。

**CBST 的特性**

完全二叉搜索树有以下几个重要的特性：

1. **高度**: CBST 的高度是 log(n+1)，其中 n 是结点的数量。
2. **叶子结点**: CBST 中所有叶子结点都位于同一层。
3. **中序遍历**: CBST 的中序遍历顺序是升序或降序。

**CBST 的应用**

完全二叉搜索树在许多场景下非常有用，例如：

1. **文件系统**: CBST 可以用于组织文件和目录的结构。
2. **数据库索引**: CBST 可以用于创建高效的数据库索引。
3. **排序算法**: CBST 可以用于实现快速排序和其他排序算法。

**CBST 的构造**

构造一个完全二叉搜索树需要遵循以下步骤：

1. **选择根结点**:选择一个初始键值作为根结点。
2. **插入结点**: 将新结点插入到合适的位置，确保 CBST 的性质不被破坏。

**CBST 的删除**

删除一个结点需要遵循以下步骤：

1. **找到待删除结点**: 找到要删除的结点。
2. **替换结点**: 将待删除结点的值替换为其子树中最小或最大值。
3. **调整 CBST**: 调整 CBST 的结构，确保其性质不被破坏。

**代码示例**

以下是 Python代码示例，展示了如何构造和操作一个完全二叉搜索树：

class Node:
 def __init__(self, key):
 self.key = key self.left = None self.right = Nonedef insert(root, key):
 if root is None:
 return Node(key)
 elif key < root.key:
 root.left = insert(root.left, key)
 else:
 root.right = insert(root.right, key)
 return rootdef delete(root, key):
 if root is None:
 return root elif key < root.key:
 root.left = delete(root.left, key)
 elif key > root.key:
 root.right = delete(root.right, key)
 else:
 if root.left is None:
 return root.right elif root.right is None:
 return root.left else:
 min_node = find_min(root.right)
 root.key = min_node.key root.right = delete(root.right, min_node.key)
 return rootdef find_min(node):
 while node.left is not None:
 node = node.left return node# 构造一个完全二叉搜索树root = Node(5)
insert(root,3)
insert(root,7)
insert(root,2)
insert(root,4)
insert(root,6)
insert(root,8)

# 删除结点delete(root,5)

# 中序遍历def inorder_traversal(node):
 if node is not None:
 inorder_traversal(node.left)
 print(node.key, end=" ")
 inorder_traversal(node.right)

inorder_traversal(root)