二叉搜索樹一維範圍搜索

二叉搜索樹通常用來保存一維的數據，而有時可能需要在這些一維的數據中搜索出所有在一個範圍內的元素。比如：一顆樹有元素 { 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 = 節點數量。

AVL 樹實現

一個 AVL 樹的 C 實現。先定義接口 avl.h：

#ifndef _AVLTREE_H_
#define _AVLTREE_H_

typedef struct avltree_t avltree_t;

/*
 * Allocates a new empty AVL tree.
 *
 * @return a pointer to the tree
 */
avltree_t* avl_alloc(void);

/*
 * Frees an AVL tree.
 *
 * @param tree  the tree to free.
 */
void avl_free(avltree_t* /*tree*/);

/*
 * Inserts into an AVL tree.
 *
 * @param elem  the element to insert
 */
void avl_insert(avltree_t* /*tree*/, int /*elem*/);

/*
 * Deletes an element from an AVL tree. Does nothing if the element is not in
 * the tree.
 *
 * @param elem  the element to delete
 */
void avl_delete(avltree_t* /*tree*/, int /*elem*/);

/*
 * Searches for an element in an AVL tree.
 *
 * @param tree      the tree to search on
 * @param needle    the element to search
 * @return          1 if `needle' is found or 0 otherwise
 */
int avl_search(avltree_t* /*tree*/, int /*needle*/);

/*
 * Graphs the tree visually using pure text.
 *
 * @param tree  the tree to graph
 */
void avl_graph(avltree_t* /*tree*/);

#endif /* _AVLTREE_H_ */

avl.h 中聲明了一個抽象數據類型 avltree_t，在 avl.c 中首先需要實現的就是這個結構。AVL 樹結構的實現方法變化很多，這裏除了常規的子節點指針和元素鍵之外只用到了一個額外的域保存子樹的高度，實則還可以用一個指針域保存父節點的地址，方便進行再平衡（rebalance）時直接通過域回溯到父節點調整高度並進行旋轉操作。下面的實現由於是通過遞歸提供的隱式棧（函數調用棧）實現回溯，所以並不需要每個節點存儲父節點地址。子樹的高度在實踐時會有一定的上限：理論上在 4GB 的 32 位取址空間中只有 4294967296 的可用字節（這還不計系統、其他程序等所需的資源），若按每個樹節點 16 字節算，最多只可能有 4194304 個節點，所以樹的高度在最好情況下只有 22 左右，而最壞也不會超過 30^[1]。這意味著每個子樹的高度只需要 5 個二進制位就能存儲，在某些空間緊張的場合下可以作為位域與其它域共享一塊整 8 位的內存。

typedef struct node_t node_t;

struct node_t
{
    int elem;
    int height;
    node_t* lchild;
    node_t* rchild;
};

struct avltree_t
{
    node_t* root;
};

基本的內存分配和釋放函數：

avltree_t*
avl_alloc(void)
{
    return calloc(1, sizeof (avltree_t));
}

void
free_nodes(node_t* root)
{
    if (root == 0)
        return;
    free_nodes(root->lchild);
    free_nodes(root->rchild);
    free(root);
}

void
avl_free(avltree_t* tree)
{
    if (tree != 0) {
        free_nodes(tree->root);
        free(tree);
    }
}

一些輔助函數，分別用於計算兩個數的最大值、計算節點高度、更新節點高度以及計算節點平衡因子。

int max(int a, int b)
{
    return a < b ? b : a;
}

/* Empty tree has height -1, tree with one node has height 0, etc. */
int height(node_t* node)
{
    return node != 0 ? node->height : -1;
}

void update_height(node_t* node)
{
    node->height = max(height(node->lchild), height(node->rchild)) + 1;
}

int bfactor(node_t* node)
{
    return height(node->lchild) - height(node->rchild);
}

旋轉操作。使用雙重間接引用是為了避免回溯操縱父節點，因為當沒有父節點引用時只要保存了父節點結構中子節點指針的地址，就可以直接通過間接引用修改父節點所引用的子節點。

/*
 * The following rotation and rebalance operations assume the input trees have
 * a height sufficiently large to perform rotations.
 */

void rotate_left(node_t** node)
{
    node_t* parent = *node;
    node_t* rchild = parent->rchild;
    node_t* rlchild = rchild->lchild;
    rchild->lchild = parent;
    parent->rchild = rlchild;
    *node = rchild;
    update_height(parent);
}

void rotate_right(node_t** node)
{
    node_t* parent = *node;
    node_t* lchild = parent->lchild;
    node_t* lrchild = lchild->rchild;
    lchild->rchild = parent;
    parent->lchild = lrchild;
    *node = lchild;
    update_height(parent);
}

再平衡函数。当平衡因子变为 2 或 -2 时，树不再符合 AVL 树的平衡特性，故而需要通过旋转操作进行再平衡。

void
rebalance(node_t** pnode)
{
    node_t* node = *pnode;
    switch (bfactor(node)) {
    /* Heavy to the left. */
    case 2:
        if (bfactor(node->lchild) == -1)
            rotate_left(&node->lchild);
        rotate_right(pnode);
        break;
    /* Heavy to the right. */
    case -2:
        if (bfactor(node->rchild) == 1)
            rotate_right(&node->rchild);
        rotate_left(pnode);
        break;
    }
}

void
adjust_tree(node_t** pnode)
{
    rebalance(pnode);
    update_height(*pnode);
}

最後是插入、刪除、搜索操作以及一個輸出函數的實現。刪除運算相較插入運算來說略為繁雜，需要考慮的場合更多，可能的再平衡次數也更多，但仍然可在 O(log n) 時間內完成。

void
insert_node(node_t** pnode, int elem)
{
    node_t* node = *pnode;
    if (node == 0) {
        node = *pnode = calloc(1, sizeof (node_t));
        node->elem = elem;
    } else {
        insert_node(elem < node->elem ? &node->lchild : &node->rchild, elem);
        adjust_tree(pnode);
    }
}

void
avl_insert(avltree_t* tree, int elem)
{
     insert_node(&tree->root, elem);
}

/* Removes and returns the leftmost child of a node. */
node_t*
remove_leftmost(node_t** pnode)
{
    node_t* node = *pnode;
    if (node->lchild == 0) {
        *pnode = node->rchild;
    } else {
        node = remove_leftmost(&node->lchild);
        adjust_tree(pnode);
    }
    return node;
}

void
delete_node(node_t** pnode, int elem)
{
    node_t* node = *pnode;
    if (node == 0) {
        return;
    } else if (elem == node->elem) {
        /* `node' is a leaf or has only one child. */
        if (node->lchild == 0) {
            *pnode = node->rchild;
        } else if (node->rchild == 0) {
            *pnode = node->lchild;
        /* `node' has two children. */
        } else {
            node_t* succ = remove_leftmost(&node->rchild);
            succ->lchild = node->lchild;
            succ->rchild = node->rchild;
            /* Replace `node' with its in-order successor. */
            *pnode = succ;
            adjust_tree(pnode);
        }
        free(node);
    } else {
        if (elem < node->elem)
            delete_node(&node->lchild, elem);
        else
            delete_node(&node->rchild, elem);
        adjust_tree(pnode);
    }
}

void
avl_delete(avltree_t* tree, int elem)
{
    delete_node(&tree->root, elem);
}

/*
 * Searches for an AVL tree node and returns a pointer to it if found or 0
 * otherwise.
 */
node_t*
search_node(node_t* node, int needle)
{
    if (node == 0)
        return 0;
    else if (needle < node->elem)
        return search_node(node->lchild, needle);
    else if (needle > node->elem)
        return search_node(node->rchild, needle);
    else
        return node;
}

int
avl_search(avltree_t* tree, int needle)
{
    return search_node(tree->root, needle) != 0;
}

void
graph_nodes(node_t* root, int level)
{
    int i;
    if (root == 0)
        return;
    graph_nodes(root->rchild, level + 1);
    for (i = 0; i < level; ++i)
        printf("    ");
    printf("%d\n", root->elem, root->height);
    graph_nodes(root->lchild, level + 1);
}

void
avl_graph(avltree_t* tree)
{
    printf("-----------------Tree-----------------\n");
    graph_nodes(tree->root, 0);
}

[1] AVL 树的高度已被证明小于 log_ϕ(2)*log₂(n+2)-1，ϕ 是黄金分割，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() 具有不变性（非破坏性），那可以操纵输入数组的复件。

用栈实现队列

队列可以通过两个栈来实现。先以 ADT 形式开放以下栈操作。

typedef struct stack_t stack_t;

stack_t* alloc_stack(void);
int empty(stack_t*);
void free_stack(stack_t*);
void push(stack_t*, int /*elem*/);
int pop(stack_t*);

为了方便看官测试，我们以单向链表实现以上接口。

#include <malloc.h>
#include <stddef.h>

struct node_t
{
    int elem;
    struct node_t* next;
};

struct stack_t
{
    struct node_t* top;
};

struct stack_t*
alloc_stack(void)
{
    return calloc(1, sizeof (struct stack_t));
}

int
empty(struct stack_t* stack)
{
    return stack->top == 0;
}

void
free_stack(struct stack_t* stack)
{
    while (!empty(stack)) {
        struct node_t* next = stack->top->next;
        free(stack->top);
        stack->top = next;
    }
    free(stack);
}

void
push(struct stack_t* stack, int elem)
{
    struct node_t* node;
    struct node_t* top = malloc(sizeof (struct node_t));
    top->elem = elem;
    top->next = stack->top;
    stack->top = top;
}

int
pop(struct stack_t* stack)
{
    int elem;
    struct node_t top;
    
    if (stack->top == 0)
        return 0;

    top = *stack->top;
    free(stack->top);
    stack->top = top.next;
    
    return top.elem;
}

用两个栈实现队列的思路是：用一个栈存储输入的数据，另一个栈负责输出。将输入的数据按顺序从输入栈 pop 并 push 到输出栈，原本的元素顺序便会反转，从后进先出变为先进先出。

struct queue_t
{
    struct stack_t* in;
    struct stack_t* out;
};

struct queue_t*
alloc_queue(void)
{
    struct queue_t* queue = malloc(sizeof (struct queue_t));
    queue->in = alloc_stack();
    queue->out = alloc_stack();
    return queue;
}

void
free_queue(struct queue_t* queue)
{
    free_stack(queue->in);
    free_stack(queue->out);
    free(queue);
}

void
enqueue(struct queue_t* queue, int elem)
{
    push(queue->in, elem);
}

int
dequeue(struct queue_t* queue)
{
    if (empty(queue->out))
        while (!empty(queue->in))
            push(queue->out, pop(queue->in));
    return pop(queue->out);
}

时间复杂度（n=队列中元素数量）：最坏场合下 dequeue()∈Ɵ(n*(push()+pop()))，平摊分析下 dequeue()∈Ɵ(pop())，而 enqueue∈Ɵ(push())。