二叉搜索樹一維範圍搜索

二叉搜索樹通常用來保存一維的數據，而有時可能需要在這些一維的數據中搜索出所有在一個範圍內的元素。比如：一顆樹有元素 { 1, 3, 5, 9, 11, 12 }，給定一個閉區間 [4, 11]，最後的搜索結果應該是 { 5, 9, 11 }。

對於範圍搜索，一個 naive 的實現可以遍歷樹的所有節點，然後輸出所有在區間範圍內的元素。這種實現的復雜度是 Ɵ(n)，n = 樹節點數量，相當於最差的線性搜索。實踐時，在二插搜索樹上的範圍搜索可以利用搜索樹有序的特性進行優化，避免一些不必要的節點訪問。範圍搜索迭代的每一步大致可以分為三個場合，我們可以通過給節點著色來區分這三個場合，即分別定義黑色節點、灰色節點以及白色節點。

搜索樹中每一個節點都隱式地與一個值域相關聯，這個值域表示了當前節點及所有其子節點的值域，也就是當前（子）樹的值域。二叉搜索樹根部節點的值域是 (-∞,∞)，而每深入一層節點，這個值域就可以被當前節點的值一分為二，分別用來與兩個子樹相關聯。比如：一顆二叉搜索樹的根部節點的值是 2，而兩個子節點的值分別是 1 和 3，那麽根部節點的值域是 (-∞,∞)，左子節點的值域是 (-∞,2]，右子節點的值域是 [2,∞)，因為左子樹的所有節點的值都必然小於等於 2，而右子樹的所有節點的值都必然大於等於 2。知曉了這個隱式的值域，就可以用來和我們範圍搜索給定的範圍進行比較，從而避免不必要的搜索。

黑色節點是所有值域是範圍搜索區間的子集的節點；白色節點是所有值域和範圍搜索區沒有交集的節點；灰色節點是非白非黑的所有節點（即節點值域和範圍搜索區間的交集並非兩個集合中任何一個的子集）。如果當前節點是黑色節點，其子節點也都將是黑色，所以可以按順序將子樹的元素輸出；如果當前節點是灰色節點，那就不能確定它的子節點是什麽顏色，於是需要在子樹上遞歸應用範圍搜索，並檢查灰色節點的值是否在區間範圍內，如果是則輸出；如果當前節點是白色節點，其子節點也都將是白色，自然什麽都不用做。所以，優化後的範圍搜索實際上就是避免了冗余地遍歷白色節點。

下面是這個算法的一個 C 接口。為了節約代碼，這個實現是直接建立在這個 AVL 樹實現之上的。

/*
 * Searches for elements within [lo, hi] in an AVL tree.
 *
 * @param tree  the tree to search on
 * @param lo    the lower bound of the range
 * @param hi    the upper bound of the range
 */
void avl_search_range(avltree_t* /*tree*/, int /*lo*/, int /*hi*/);

為了簡化實現，avl_search_range 直接把元素輸出到了標準輸出設備。實踐時可能會需要輸出到一容器中並返回給調用者。

#include <limits.h>

void
print_inorder(node_t* node)
{
    if (node == 0)
        return;
    print_inorder(node->lchild);
    printf("%d ", node->elem);
    print_inorder(node->rchild);
}

void
search_range(node_t* node, int lo, int hi, int left, int right)
{
    if (node == 0)
        return;
    /* Black node. */
    else if (lo <= left && right <= hi)
        print_inorder(node);
    /* Gray node. */
    else if (left <= hi && lo <= right) {
        int elem = node->elem;
        search_range(node->lchild, lo, hi, left, elem);
        if (lo <= elem && elem <= hi)
            printf("%d ", elem);
        search_range(node->rchild, lo, hi, elem, right);
    }
}

void
avl_search_range(avltree_t* tree, int lo, int hi)
{
    search_range(tree->root, lo, hi, INT_MIN, INT_MAX);
    printf("\n");
}

遞歸調用時，為了讓輸出的元素按順序排列需要先進行左子樹的遞歸，然後檢查並輸出當前節點元素，最後進行右子樹的遞歸。avl_search_range∈Ɵ(k+log(n))，k = 範圍搜索區間大小，n = 節點數量。

Counting Sort（计数排序）

在满足了输入的元素属于一个有限集合的前提下，counting sort 可以在线性时间内完成排序。Counting sort 的算法过程中没有比较过一次元素，它是通过元素的键及出现的频率来决定元素按顺序排列后的位置。这有别于基于比较的排序算法，如归并排序、快速排序、插入排序，在最好的情况下也至少需要线性对数级时间（n*log(n)）完成排序（这个可以通过构建决策树来证明，当 n = 节点数量时，决策树的高度不会小于 n*log(n)）。

Counting sort 的思想是：建立一个元素出现的频率表，通过查找每个元素出现的频率可得知元素最后应排列在什么位置。

先假设元素的键就是元素的值，且属于 { 0, 1, …, k } 这个集合，这是最简单的一种情况。如：对于 [ 1, 0, 4, 0, 3 ] 这个数组，其元素属于的有限集合为 { 0, 1, 2, 3, 4 }，k=4，集合大小为 5，而 freq(0)=2, freq(1)=1, freq(2)=0, freq(3)=1, freq(4)=1。如此便知两个 0 必在最前，1 前面有两个元素（0），2 没有出现，3 前面有两个元素（0）加上一个元素（1），4 前面有有两个元素（0）加上一个元素（1）再加上一个元素（3）。由于假设了元素的键就是元素的值，在频率表构建完成后可以按键的大小顺序遍历整个频率表，依次在输出数组末尾添加频率那么多个的键，最后整个输出数组就是已经排序完成的输入数组了。如果没有作出上述假设，这里添加的就必须是频率那么多个的值。

可以用 C 来实现上述过程。频率表 count 是一个数组，其索引是元素的键，其值是频率，如 count[2] 是 2 出现的频率。这里的 arr 是输入数组，size 是数组大小，而 bound 相当于上述的 k+1，{ 0, …, k } 的大小。

void
counting_sort(int arr[], int size, int bound)
{
    int i;
    int* count = calloc(bound, sizeof (int));

    /* Construct frequency table. */
    for (i = 0; i < size; ++i)
        ++count[arr[i]];
    /* Append to output array based on frequency. */
    for (i = 0; i < bound; ++i)
        while (--count[i] >= 0)
            *arr++ = i;
}

这是一个简洁明了的实现，时间复杂度∈Ɵ(size+bound)，空间复杂度∈Ɵ(bound)。由于元素只是简单的整数，也不需要考虑排序算法稳定性的问题，因为两个值相等的整数通常被认为是不可区分的。然而，当元素的键并不是元素的值时，这个实现就不靠谱了——不能直接 *arr++ = i，而需要 *arr++ = value(i)。key(value) 可以由调用者提供，那 value(key) 呢？强行按照以上思路来实现还需要一个键到多个值的映射。稳定性也是个问题。

不妨换一种思路：保存元素的累积频率（即元素本身出现的频率加上所有更小的元素出现的频率之和），通过一个元素的累积频率可得知小于等于该元素的所有元素的频率之和，也就能直接确定元素最终的位置了。比如：元素的累积频率为 10，说明一共有 10 个小于等于该元素的元素（包括該元素本身），那么该元素应该被放在输出数组的第 10 个元素的位置上。用这种方式的话就可以通过遍历元素的值来实现，也就能访问元素的值本身了。

void
counting_sort(void* arr[], int size, int bound, int (*key)(void*))
{
    int i;
    int* count = calloc(bound, sizeof (int));
    void** sorted = malloc(size * sizeof (void*));

    /* Construct frequency table. */
    for (i = 0; i < size; ++i)
        ++count[key(arr[i])];
    /* Construct cumulative frequency table. */
    for (i = 1; i < bound; ++i)
        count[i] += count[i - 1];
    /* Sort based on key positions. Iterate backwards to be stable. */
    for (i = size - 1; i >= 0; --i)
        sorted[--count[key(arr[i])]] = arr[i];
    memcpy(arr, sorted, size * sizeof (void*));
}

这种实现的时间复杂度同样∈Ɵ(size+bound)，但空间复杂度∈Ɵ(size+bound)，因为需要额外使用 size 大小的数组作为临时存储。

需要注意的有两点：一是最后一个循环是反向迭代，二是每次要递减累积的频率。后者是针对相等元素的特殊处理——累积频率指定的是相等的元素中最后一个元素（离数组开头最远）的位置，那么下一次遇到相等元素时就应该朝数组开头移动一个索引，这样才不会导致所有相等的元素都被放到了同一个位置。另一方面，为了保证稳定性，这个过程必须与反向迭代配合，因为如果正向迭代，相等元素中先出现的反而会被放到离数组开头更远的位置。这个算法可以通过改变累积频率的存储方式来反转：如果一个元素的累积频率变为不包括该元素本身及相等元素的频率而只是小于它的元素的频率之和，那便可以从 0 迭代到 size-1，并且每次递增累积频率。

测试：

int
key(void* value)
{
    switch ((uintptr_t) value) {
    case 0:
    case 1:
    case 2:
    case 3:
        return (int) value;
    case 5:
        return 4;
    case 7:
        return 5;
    case 9:
        return 6;
    }
}

int
main()
{
    uintptr_t arr[] = { 3, 0, 9, 1, 0, 5, 7, 2, 5 };
    int i, size = sizeof (arr) / sizeof (uintptr_t);
    counting_sort((void**) arr, size, 7, key);
    //{
    for (i = 0; i < size; ++i)
        printf("%d ", arr[i]);
    printf("\n");
    //} => 0 0 1 2 3 5 5 7 9

    return 0;
}

这里的 key() 纯粹是为了测试目的而定义的完美散列函数，测试代码中出现的 7 个唯一的整数将会被完美地映射到 0..6 这 7 个键。

由于 counting sort 的前提是输入的元素属于一个有限集合，并且在计算过程中将会使用这个集合那么大的额外空间，它并不是一种通用的排序算法。实践时，通用的排序算法通常需要能够处理所有 16、32 甚至是 64 位整数，其值域的大小通常大于物理内存所能容纳的空间。基于 counting sort 之上的radix sort（基数排序）则是一个典型的可通用于更大范围值域的非比较的排序算法。

Quickselect（快速选择）

Quickselect 的思想与 quicksort 基本一致。每次 partition() 结束后可得知 pivot 的位置，自然也就知道 pivot 前后各有多少小于、大于 pivot 的元素。选择时，第 k 大的元素必然只存在于 pivot 的左边或者右边。如果 pivot 前的元素数量多于 k，则说明左边有多于 k 个元素小于 pivot，所以第 k 大的元素必然在左边，可在左边选择第 k 大元素；如果 pivot 前的元素数量少于 k，则说明左边只有不到 k 个小于 pivot 的元素，那么第 k 大的元素必然在右边，可在右边选择第 (k – (pivot 左边元素数量)) 大的元素。如此递归进行，如果 pivot 刚好是第 k 个元素，那选择过程就结束了。

Quickselect 与 quicksort 类似，拥有平摊后可观的时间复杂度，但极差的最坏情况下的复杂度。Quickselect 的平摊复杂度是 Ɵ(n)，而最坏情况下复杂度是 Ɵ(n²)，n = 元素数量。最坏情况的高阶可通过随机化算法避免，此同 quicksort。另外，由于 quickselect 递归时每一步都只需深入 pivot 左或右其中一边，其算法可以轻易地被优化为循环形式的尾调用。

一个非随机化的 C 实现如下：

int
partition(int arr[], int i, int j)
{
    int pivot = arr[i];

    for(;;) {
        for (;;) {
            if (i >= j) {
                goto done;
            } else if (arr[j] < pivot) {
                arr[i++] = arr[j];
                break;
            }
            --j;
        }
        for (;;) {
            if (i >= j) {
                goto done;
            } else if (arr[i] > pivot) {
                arr[j--] = arr[i];
                break;
            }
            ++i;
        }
    }
done:
    arr[i] = pivot;

    return i;
}

int
qselect(int arr[], int i, int j, int k)
{
    for (;;) {
        int pivot = partition(arr, i, j);
        int pivot_pos = pivot - i + 1;
        if (pivot_pos == k)
            return arr[pivot];
        if (pivot_pos > k) {
            j = pivot - 1;
        } else {
            i = pivot + 1;
            k -= pivot_pos;
        }
    }
}

测试：

    int arr[] = {3, 2, -32, 1442, 203, 37, 874, 2, 193, 34};
    int right_bound = sizeof (arr) / sizeof (int) - 1;

    printf("%d\n", qselect(arr, 0, right_bound, 1)); // => -32
    printf("%d\n", qselect(arr, 0, right_bound, 2)); // => 2
    printf("%d\n", qselect(arr, 0, right_bound, 5)); // => 34
    printf("%d\n", qselect(arr, 0, right_bound, 4)); // => 3

目前这个实现中的 partition() 是原地破坏性算法。如果需要 qselect() 具有不变性（非破坏性），那可以操纵输入数组的复件。

Ruby 之“Schwartzian 變換”

Ruby 的 Array#sort 和 Array#sort_by 在實現上有微妙差異。Array#sort 通過在每次迭代過程中直接比較元素来進行排序，而 Array#sort_by 在排序之餘還進行了一種優化，試圖減少計算元素“键”時帶來的開銷。

這裡所謂的“键”是用來衡量两个元素孰大孰小的一個標準，在元素是標量類型（即並非兩個或兩個以上域的複合結構）的情況下，鍵通常就是元素本身的值的大小；在元素是兩個或兩個以上域的複合結構時，鍵則通常是其域值的一個組合。比如，字符串可以看作是擁有 n 個字符域的複合結構，而在進行字符串排序時常用到的字典順序，就可以看作是所有字符域組合之下得出的鍵。

鍵的計算有時是昂貴的，而特定的排序算法在迭代過程中往往都需要多次獲取同一個元素的鍵，這就使得冗餘的鍵計算給整個排序帶來了不可磨滅的開銷。Array#sort_by 採用的優化技巧，實際上就是緩存優化（Memoization）的一個特例。所有元素的鍵都事先被 Array#sort_by 計算好，並和元素本身關聯在一起，儲存到另一個表中。之後對該表中計算好的鍵進行排序就同時排列了與之關聯的元素本身。最後，拋棄表中的鍵而返回所有元素本身，排序就完成了。這個優化在 Perl 編程中被反復地運用，最終成為了一個廣為人知的編程手法——“Schwartzian 變換”。在 Lisp 編程中，同樣的手法被稱為“decorate-sort-undecorate”。

Ruby 可以如下般實現 Schwartzian 變換：

class Array
  def my_sort
    map { |e| [ e, e.key ] }.sort { |a, b| a[1] <=> b[1] }.map { |e| e[0] }
  end
end

這和 Perl 的參考實現如出一轍（感謝 Ruby 的發散性！）——

@sorted = map  { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map  { [$_, foo($_)] }
               @unsorted;

可以簡單地來測試一下實際執行時的效率差別。首先給 Fixnum 打一個猴子補丁：

class Fixnum
  def key
    sleep 0.1
    self
  end
end

如此就可以在排列 Fixnum 時通過 Fixnum#key 這個“昂貴”的函數來獲取鍵。睡眠線程的語句只是為了偽造函數的開銷。

require 'benchmark'
include Benchmark

array = [3, 1, 2, 4]

bm(10) do |b|
  b.report('sort')    { array.sort { |a, b| a.key <=> b.key } }
  b.report('my_sort') { array.my_sort                         }
  b.report('sort_by') { array.sort_by { |e| e.key }           }
end

筆者本機輸出：

                user     system      total        real
sort        0.000000   0.000000   0.000000 (  1.000057)
my_sort     0.000000   0.000000   0.000000 (  0.400023)
sort_by     0.000000   0.000000   0.000000 (  0.400023)

可見 Array#sort 相比於 Array#sort_by 和 Array#my_sort 慢了許多。由於鍵計算函數的開銷是通過睡眠線程偽造的，所以雖然掛鐘時間不是零，但用戶時間加系統時間卻是零。

當然，Schwarzian 變換只是針對昂貴鍵計算排序的一種手法。很多時候我們都僅僅是在排列簡單的鍵，比如 Fixnum （或其它整型數據類型）本身，那附帶了 Schwarzian 變換的 Array#sort_by 由於多做了緩存鍵的工作，效率上自然就不如 Array#sort 了。

用 MIPS 汇编语言实现快速排序

一个用 MIPS 汇编语言实现的快速排序。这里使用的 MIPS 指令仅仅是真实 MIPS 机器指令集的一小一部分，同时又扩充了一些如 jalr（用来在 jr 之前把返回地址存入 $31）之类的方言式指令。程序默认 $1 保存了内存中一个数组的首地址，$2 是其长度。程序入口点是一段测试代码，调用快速排序将数组排序，并找到所有元素的中数，保存到 $3 中。

;; entry point

        sw      $31,    -4($30)
        lis     $31
        .word   4
        sub     $30,    $30,    $31

        lis     $4
        .word   0
        mult    $2,     $31
        mflo    $5
        sub     $5,     $5,     $31
        lis     $29
        .word   qsort
        jalr    $29                                     ; call qsort to sort the array

        lis     $31
        .word   4
        add     $30,    $30,    $31
        lw      $31,    -4($30)

;; find the element at the midpoint of the sorted array
        lis     $4
        .word   2
        div     $2,     $4
        mflo    $4
        lis     $5
        .word   4
        multu   $4,     $5
        mflo    $4
        add     $4,     $4,     $1

        lw      $3,     0($4)

        jr      $31

;;
;; qsort
;;
;; $1 <- address of array
;; $3 <- return value
;; $4 <- @param - left bound
;; $5 <- @param - right bound
;; $6 <- left pointer
;; $7 <- right pointer
;; $8 <- pivot
;; $28 <- temporary storage
;; $29 <- temporary storage

qsort:
;; store registers used
	sw	$4,	-4($30)
	sw	$5,	-8($30)
	sw	$6,	-12($30)
	sw	$7,	-16($30)
	sw	$8,	-20($30)
	sw	$28,	-24($30)
	sw	$29,	-28($30)

;; base case
	slt	$29,	$4,	$5
	beq	$29,	$0,	ret			; if left bound >= right bound then return

;; initialization
        add     $6,     $4,     $1
        add     $7,     $5,     $1
        lw      $8,     0($6)                           ; pivot = *lp


;; main loop - while left pointer = pivot

        lw      $29,    0($7)
        slt     $28,    $29,    $8
        bne     $28,    $0,     bilp1

        lis     $28
        .word   4
        sub     $7,     $7,     $28                     ; rp -= 1

        beq     $0,     $0,     olp
bilp1:
;; inner loop 1 - break

        sw      $29,    0($6)                           ; *lp = *rp
        lis     $28
        .word   4
        add     $6,     $6,     $28                     ; lp += 1

;; inner loop 2 - while *lp = rp) break outer loop

        lw      $29,    0($6)
        slt     $28,    $29,    $8
        beq     $28,    $0,     bilp2

        lis     $28
        .word   4
        add     $6,     $6,     $28                     ; lp += 1

        beq     $0,     $0,     ilp2
bilp2:
;; inner loop 2 - break

        sw      $29,    0($7)                           ; *rp = *lp
        lis     $28
        .word   4
        sub     $7,     $7,     $28                     ; rp -= 1

        beq     $0,     $0,     olp
bolp:
;; main loop - break

        sw      $8,     0($6)                           ; *lp = pivot

;; recurse left
        lw      $4,     -4($30)

        sw      $31,    -32($30)
        lis     $31
        .word   32
        sub     $30,    $30,    $31

        lis     $29
        .word   4
        sub     $5,     $6,     $29                     ; right bound = lp - $1 - 1
        sub     $5,     $5,     $1
        lis     $29
        .word   qsort
        jalr    $29

        lis     $31
        .word   32
        add     $30,    $30,    $31
        lw      $31,    -32($30)

; recurse right
        lw      $5,     -8($30)

        sw      $31,    -32($30)
        lis     $31
        .word   32
        sub     $30,    $30,    $31

        lis     $29
        .word   4
        add     $4,     $6,     $29                     ; left bound = lp -$1 + 1
        sub     $4,     $4,     $1
        lis     $29
        .word   qsort
        jalr    $29

        lis     $31
        .word   32
        add     $30,    $30,    $31
        lw      $31,    -32($30)

ret:
;; restore registers used
        lw      $29,    -28($30)
        lw      $28,    -24($30)
        lw      $8,     -20($30)
        lw      $7,     -16($30)
        lw      $6,     -12($30)
        lw      $5,     -8($30)
        lw      $4,     -4($30)

        jr      $31