GC03-寻找二叉排序树中最大值和最小值结点¶

算法原理¶

二叉排序树性质回顾¶

左子树：所有结点值 < 根结点值
右子树：所有结点值 > 根结点值
中序遍历：得到有序序列

最值查找原理¶

最小值：最左下角的结点（左子树链的末端）
最大值：最右下角的结点（右子树链的末端）

代码实现¶

C
/**
 * 查找二叉排序树中最小值结点
 * 参数：bt - 二叉排序树根结点
 * 返回值：指向最小值结点的指针
 */
BiTree Min(BiTree bt) {
    // 边界检查：空树情况
    if (bt == NULL) {
        return NULL;
    }

    // 沿着左子树链一直向下找，直到最左下角
    while (bt->lchild != NULL) {
        bt = bt->lchild;
    }

    // 返回最小值结点
    return bt;
}

/**
 * 查找二叉排序树中最大值结点
 * 参数：bt - 二叉排序树根结点
 * 返回值：指向最大值结点的指针
 */
BiTree Max(BiTree bt) {
    // 边界检查：空树情况
    if (bt == NULL) {
        return NULL;
    }

    // 沿着右子树链一直向下找，直到最右下角
    while (bt->rchild != NULL) {
        bt = bt->rchild;
    }

    // 返回最大值结点
    return bt;
}

/**
 * 获取最小值（返回值而非结点指针）
 */
ElemType getMinValue(BiTree bt) {
    BiTree minNode = Min(bt);
    if (minNode != NULL) {
        return minNode->data;
    }
    return -1; // 或其他表示错误的值
}

/**
 * 获取最大值（返回值而非结点指针）
 */
ElemType getMaxValue(BiTree bt) {
    BiTree maxNode = Max(bt);
    if (maxNode != NULL) {
        return maxNode->data;
    }
    return -1; // 或其他表示错误的值
}

执行过程详解¶

示例演示¶

C
// 二叉排序树示例：
//       50
//      /  \
//    30    70
//   / \   /  \
//  20 40 60  80
// /          /  \
// 10        75   90

// 查找最小值过程：
// 从根结点50开始
// 50 → 30 → 20 → 10
// 10没有左孩子，所以10是最小值

// 查找最大值过程：
// 从根结点50开始
// 50 → 70 → 80 → 90
// 90没有右孩子，所以90是最大值

执行轨迹图解¶

Text Only

最小值查找路径：
50 → 30 → 20 → 10 (终止)

最大值查找路径：
50 → 70 → 80 → 90 (终止)

查找过程中的比较次数：
- 最小值：4次比较
- 最大值：4次比较

复杂度分析¶

时间复杂度¶

最好情况（完全平衡树）¶

树高度：O(log N)
查找路径长度：O(log N)
时间复杂度：O(log N)

最坏情况（退化为链表）¶

Text Only
1 2 3 4 5 6 7 8 9 10 11	`退化为右斜树： 10 \ 20 \ 30 \ 40 查找最小值：需要从40 → 30 → 20 → 10 时间复杂度：O(N)`

平均情况¶

平衡二叉排序树的平均高度：O(log N)
时间复杂度：O(log N)

空间复杂度¶

迭代版本（给定代码）¶

只使用常数个局部变量
空间复杂度：O(1)

递归版本（扩展）¶

C
BiTree Min_Recursive(BiTree bt) {
    if (bt == NULL) return NULL;
    if (bt->lchild == NULL) return bt;
    return Min_Recursive(bt->lchild);
}
// 递归深度：O(h)，空间复杂度：O(log N) 或 O(N)

算法正确性证明¶

最小值正确性证明¶

命题：在二叉排序树中，最小值结点一定是沿着左子树链到达的最左下角结点。

证明： 1. 设最小值结点为 M 2. 假设 M 不是最左下角结点，则 M 有左孩子 L 3. 根据 BST 性质：L < M 4. 这与 M 是最小值矛盾 5. 因此 M 必须没有左孩子，即为最左下角结点

最大值正确性证明¶

命题：在二叉排序树中，最大值结点一定是沿着右子树链到达的最右下角结点。

证明： 1. 设最大值结点为 M 2. 假设 M 不是最右下角结点，则 M 有右孩子 R 3. 根据 BST 性质：R > M 4. 这与 M 是最大值矛盾 5. 因此 M 必须没有右孩子，即为最右下角结点

优化版本¶

1. 带错误处理的版本¶

C
/**
 * 安全版本：包含完整的错误检查
 */
BiTree Min_Safe(BiTree bt) {
    // 空树检查
    if (bt == NULL) {
        return NULL;
    }

    // 确保是有效的BST
    if (bt->lchild == NULL) {
        return bt;
    }

    // 迭代查找最小值
    BiTree current = bt;
    while (current->lchild != NULL) {
        current = current->lchild;
    }
    return current;
}

BiTree Max_Safe(BiTree bt) {
    // 空树检查
    if (bt == NULL) {
        return NULL;
    }

    // 确保是有效的BST
    if (bt->rchild == NULL) {
        return bt;
    }

    // 迭代查找最大值
    BiTree current = bt;
    while (current->rchild != NULL) {
        current = current->rchild;
    }
    return current;
}

2. 递归版本¶

C
/**
 * 递归实现版本
 */
BiTree Min_Recursive(BiTree bt) {
    // 基础情况：空树或没有左孩子
    if (bt == NULL || bt->lchild == NULL) {
        return bt;
    }

    // 递归查找左子树的最小值
    return Min_Recursive(bt->lchild);
}

BiTree Max_Recursive(BiTree bt) {
    // 基础情况：空树或没有右孩子
    if (bt == NULL || bt->rchild == NULL) {
        return bt;
    }

    // 递归查找右子树的最大值
    return Max_Recursive(bt->rchild);
}

3. 同时查找最大最小值¶

C
/**
 * 同时查找最大值和最小值
 */
typedef struct {
    BiTree minNode;
    BiTree maxNode;
} MinMaxResult;

MinMaxResult findMinMax(BiTree bt) {
    MinMaxResult result = {NULL, NULL};

    if (bt == NULL) {
        return result;
    }

    // 查找最小值
    result.minNode = Min(bt);

    // 查找最大值
    result.maxNode = Max(bt);

    return result;
}

实际应用场景¶

1. 数据库索引范围查询¶

C
// 在B+树索引中查找范围
RangeResult findRange(BiTree index, int low, int high) {
    int minVal = getMinValue(index);
    int maxVal = getMaxValue(index);

    // 优化：如果查询范围超出数据范围，可以直接返回
    if (low > maxVal || high < minVal) {
        return emptyRange();
    }

    // 执行实际的范围查询
    return performRangeQuery(index, low, high);
}

2. 优先队列实现¶

C
// 基于BST的优先队列
typedef struct {
    BiTree root;
} BSTPriorityQueue;

// 获取最高优先级元素（最大值）
ElemType getHighestPriority(BSTPriorityQueue* pq) {
    BiTree maxNode = Max(pq->root);
    return maxNode ? maxNode->data : -1;
}

// 获取最低优先级元素（最小值）
ElemType getLowestPriority(BSTPriorityQueue* pq) {
    BiTree minNode = Min(pq->root);
    return minNode ? minNode->data : -1;
}

3. 统计分析应用¶

C
// 数据分析中的最值统计
typedef struct {
    int minValue;
    int maxValue;
    int count;
} DataStats;

DataStats analyzeBSTData(BiTree root) {
    DataStats stats;
    BiTree minNode = Min(root);
    BiTree maxNode = Max(root);

    stats.minValue = minNode ? minNode->data : 0;
    stats.maxValue = maxNode ? maxNode->data : 0;
    stats.count = countNodes(root); // 另一个辅助函数

    return stats;
}

与其他算法的比较¶

与线性查找的比较¶

C
// 线性查找数组中的最值（无序数组）
int findMin_Array(int arr[], int n) {
    int min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    return min;
}
// 时间复杂度：O(N)

// BST查找最值
int findMin_BST(BiTree root) {
    BiTree minNode = Min(root);
    return minNode ? minNode->data : -1;
}
// 时间复杂度：O(log N) 平均情况

与堆结构的比较¶

结构	查找最小值	查找最大值	插入	删除
BST	O(log N)	O(log N)	O(log N)	O(log N)
最小堆	O(1)	O(N)	O(log N)	O(log N)
最大堆	O(N)	O(1)	O(log N)	O(log N)

理论扩展¶

1. 平衡二叉搜索树中的性能保证¶

C
// 在AVL树或红黑树中
// 由于树高度保证为O(log N)
// 查找最值的时间复杂度严格为：O(log N)

2. 动态维护最值¶

C
// 在插入删除操作中维护最值缓存
typedef struct {
    BiTree root;
    BiTree cachedMin;
    BiTree cachedMax;
    bool minValid;
    bool maxValid;
} OptimizedBST;

// 插入时更新缓存
void insertAndUpdateCache(OptimizedBST* bst, int value) {
    insert(bst->root, value);
    bst->minValid = false; // 标记缓存失效
    bst->maxValid = false;
}

// 延迟计算最值
BiTree getMinCached(OptimizedBST* bst) {
    if (!bst->minValid) {
        bst->cachedMin = Min(bst->root);
        bst->minValid = true;
    }
    return bst->cachedMin;
}

3. 多维最值查找¶

C
// 在二维BST中查找最值
typedef struct {
    int x, y;
} Point;

// 查找x坐标最小的点
BiTree findMinX(BiTree root) {
    if (root == NULL) return NULL;
    while (root->lchild != NULL) {
        root = root->lchild;
    }
    return root;
}

总结¶

二叉排序树最值查找算法体现了数据结构特性利用的思想：

核心优势¶

高效性：利用BST性质，避免全树遍历
简洁性：算法逻辑简单直观
实用性：在实际应用中广泛使用

关键要点¶

理解BST性质：左小右大是算法正确性的基础
边界处理：正确处理空树和叶结点情况
复杂度分析：区分最好、最坏、平均情况

应用价值¶

数据库索引优化
算法竞赛常用技巧
系统编程基础算法
数据结构教学经典案例

这是二叉搜索树最基本也是最重要的操作之一，体现了利用数据结构特性优化算法的设计思想，在计算机科学中具有重要地位。