折半查找判定树内部结点

### 折半查找判定树中的内部结点

#### 定义与特性
折半查找判定树是一种用于表示折半查找过程的二叉树结构。该树具有特定性质，使得其能够高效地执行查找操作。当 \( n>0 \) 时，折半查找判定树的根节点为 \( mid=\frac{n+1}{2} \)，此位置决定了后续左右子树的划分[^1]。

对于任意一个内部节点而言：

- **左子树**：由数组中小于中间值的部分构成；
- **右子树**：由大于中间值的部分组成；
- **平衡性**：无论序列长度是奇数还是偶数，左子树的节点数目总是不大于右子树的节点数目。具体来说，若序列总长 \( n \) 是奇数，则左右子树节点个数相同；若是偶数，则左子树节点数比右子树少一个[^2]。

这种设计确保了每次比较都能有效地缩小一半范围，从而提高了搜索效率。

#### 构建原则
构建折半查找判定树的过程遵循一定的规则来保持上述提到的关键属性。例如，在处理偶数个元素的情况下，通过向下取整的方式确定 `mid` 值，这会使得左侧分支拥有较少的数量，而右侧则多出一个元素[^3]。相反，采用向上取整的方法会使左侧稍微更多一些。

此外，为了维持树的高度尽可能低并接近完全二叉树的形式，通常会选择最靠近中心的位置作为新的分割点。这样做的好处是可以最小化最大路径长度，进而优化平均情况下的性能表现[^4]。

def build_binary_search_tree(data_list):
    if not data_list:
        return None
    
    def helper(low, high):
        if low > high:
            return None
        
        # 计算中间索引 (考虑不同取整方式的影响)
        mid = (low + high) // 2
        
        node = TreeNode(data_list[mid])
        
        # 递归创建左右子树
        node.left = helper(low, mid - 1)
        node.right = helper(mid + 1, high)

        return node
    
    root = helper(0, len(data_list)-1)
    
    return root