二分查找与二叉搜索树

复习定位

二分查找是最基本的查找算法——每步将查找范围缩小一半。前提是数据已经排序且能够随机访问(数组)。BST是二叉树结构——左子树所有节点<根<右子树所有节点——中序遍历BST得到升序序列。BST在理想平衡时查找O(log n)——但最坏(插入已排序数据)退化为链表O(n)——所以需要AVL平衡二叉树的平衡旋转操作保证树的高度始终为log n。

二分查找

二分查找的思想——每次比较中间元素与目标值——如果相等则找到；如果目标<中间则到左半部分继续；否则到右半部分继续。每次将查找范围缩小一半——2^n范围→n次比较——所以时间复杂度O(log n)。

实现时要特别小心边界条件：

int binary_search(int arr[], int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high - low) / 2;  // 防止溢出
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;  // 未找到
}

mid = (low + high) / 2在low+high大于INT_MAX时可能溢出为负数——所以标准写法是low + (high - low) / 2或位运算(low + high) >>> 1(Java)。

变体——查找第一个等于target、最后一个等于target——边界条件有细微差别。

BST的查找

BST的查找——从根开始——目标值比当前结点小则左走——比当前大则右走——直到找到或到达null。

Node* search(Node* root, int key) {
    if (root == NULL || root->key == key) return root;
    if (key < root->key) return search(root->left, key);
    else return search(root->right, key);
}

查找的时间复杂度取决于树的高度。高度越小——比较越少。

BST的删除

删除分为三种情况：

1. 叶子结点——直接删除——父结点指向该叶子的指针设为null。
2. 有一个孩子——用孩子顶替被删除的结点——让父结点的指针直接指向孩子的孩子。
3. 有两个孩子——将被删除结点的右子树中的最小结点(中序后继)的值替换到当前结点——然后递归删除那个被选为后继的节点(原来在于右子树的最小值)它最多只有一个右孩子——因此退化为情况1或2。

BST的退化与平衡

如果向空BST插入序列[1,2,3,4,5]——每次新结点都成为根的右孩子——形成一条只有右孩子的链——查找5需要遍历5个结点——O(n)——和链表一样差。因此需要平衡——二叉树的旋转操作——如AVL树限制任意结点的左右子树高度差不超过1——保证高度≈log n——使查找稳定在O(log n)。红黑树通过染色(红/黑)和旋转保证最长路径不超过最短路径的2倍也是O(log n)——但插入所需的旋转比AVL更少。

复习检查

1. 二分查找中mid = low + (high - low) / 2——为什么(low + high) / 2可能溢出？low=2^30,high=230——(low+high)溢出为负值——而low + (high-low)/2只做减法——减法极不可能超过int范围。

2. BST退化为链表的输入序列举例——输入序列已经是递增有序——插入空BST——得到一条右斜链——查找任何大于1的结点复杂度O(n)。

3. 删除BST中具有两个孩子的结点时——为什么要用右子树的最小结点(中序后继)替换而非任意其他结点——后继替换后为何保持了BST性质(右子树除后继外的所有结点仍然大于替代值——左子树所有结点小于它)？

4. BST和二分查找都能查找——但一个通过指针结构、一个通过数组下标——各有什么优缺点？BST插入O(log n)比顺序表O(n)插入更高效——而二分查找需要一个可随机读的数组(下标读取O(1))而不只是链式结构。

5. AVL树比BST严格平衡多了——为什么在数据库索引中没有更大范围使用(因为磁盘I/O导向)B+树使用高扇出而非二叉结构??