对有序表进行折半查找判定树

### 关于有序表进行折半查找判定树的概念

对于长度为 n 的有序表，其对应的折半查找判定树是一种特殊的二叉树结构。当 n=0 时，该树为空；而当 n>0 时：

- 根节点代表的是位于中间位置 mid=(n+1)/2 处的数据项。
- 左子树对应着前一半较小的部分 r[1]~r[mid−1] 构成的新有序列表所形成的折半查找判定树[^1]。
- 右子树则由较大一部分即 r[mid+1]~r[n] 组成新的有序序列建立起来的折半查找判定树。

这种结构使得每次比较都能排除掉大约一半数量级的可能性，从而大大提高了搜索效率，时间复杂度达到 O(log₂n)[^2]。

### 长度为 18 的顺序存储有序表的折半查找判定树构建过程

为了具体展示如何创建一棵针对含有 18 个元素的数组执行折半查找操作所需的判定树，下面给出 Python 编程语言中的实现方式：

class TreeNode:
    def __init__(self, value=None):
        self.value = value
        self.left = None
        self.right = None


def build_binary_search_tree(arr):
    if not arr:
        return None
    
    mid_index = (len(arr)) // 2
    root = TreeNode(arr[mid_index])
    
    # Recursively construct the left subtree with elements before mid.
    root.left = build_binary_search_tree(arr[:mid_index]) 
    
    # Recursively construct the right subtree with elements after mid.
    root.right = build_binary_search_tree(arr[mid_index + 1:]) 

    return root


# Example usage for an array of length 18.
sorted_array_example = list(range(1, 19))
bst_root_node = build_binary_search_tree(sorted_array_example)

上述代码片段定义了一个简单的 `TreeNode` 类来表示单个节点，并通过递归函数 `build_binary_search_tree()` 来按照给定规则构造整棵树。这里假设输入是一个已经排好序且不含重复值的列表 `arr`，其中包含了要被索引的所有数值。

### 平均查找长度计算

平均查找长度是指在一个特定大小 N 的集合上随机选取关键字 k 进行成功定位所需经过的关键字比较次数期望值 E(N)，可以利用以下公式近似估算:

\[E(N)=\sum_{i=1}^{N}\frac{D_i}{N}, \]

其中 \( D_i\) 表示第 i 层上的内部路径总长加上外部路径总长的一半。对于平衡良好的完全二叉树来说，在最坏情况下的最大深度接近 log₂N ，因此整体性能表现良好。