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 是节点（元素）数量。

用栈实现队列

队列可以通过两个栈来实现。先以 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())。

用队列实现栈

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

typedef struct queue_t queue_t;

queue_t* alloc_queue(void);
void free_queue(queue_t*);
void enqueue(queue_t*, int /*elem*/);
int dequeue(queue_t*);
int size(queue_t*);

为了方便看官测试，我们以动态数组实现以上接口。

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

struct queue_t
{
    int* arr;
    size_t cap;
    size_t size;
};

struct queue_t*
alloc_queue(void)
{
    struct queue_t* queue = malloc(sizeof (struct queue_t));
    queue->cap = 2;
    queue->arr = malloc(queue->cap * sizeof (int));
    queue->size = 0;
    return queue;
}

void
free_queue(struct queue_t* queue)
{
    free(queue->arr);
    free(queue);
}

void
enqueue(struct queue_t* queue, int elem)
{
    if (queue->size >= queue->cap) {
        queue->cap *= 2;
        queue->arr = realloc(queue->arr, queue->cap * sizeof (int));
    }
    queue->arr[queue->size++] = elem;
}

int
dequeue(struct queue_t* queue)
{
    int elem;

    if (queue->size == 0)
        return 0;
    elem = queue->arr[0];
    memmove(queue->arr, queue->arr + 1, --queue->size * sizeof (int));
    return elem;
}

int
size(struct queue_t* queue)
{
    return queue->size;
}

以一个队列实现栈的思路是：将队列头部的元素重新添加到队列尾部，直到原队列尾部的元素被推到头部。此时队列中除头部外，其余元素的顺序依旧，如果进行 dequeue 操作，返回的便是最近一次添加到队列中的元素，也就满足了栈后进先出的特性，而对于整个队列来说便如同移除了尾部元素。

struct stack_t
{
    queue_t* queue;
};

struct stack_t*
alloc_stack(void)
{
    struct stack_t* stack = malloc(sizeof (struct stack_t));
    stack->queue = alloc_queue();
    return stack;
}

void
free_stack(struct stack_t* stack)
{
    free_queue(stack->queue);
    free(stack);
}

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

int
pop(struct stack_t* stack)
{
    int i;

    for (i = 1; i < queue; ++i)
        enqueue(stack->queue, dequeue(stack->queue));
    return dequeue(stack->queue);
}

以上是在每次 pop 时将队列尾部推至队列头部。我们也可以采用抢先模式在 push 时就为 pop 做好准备工作。每次 push 时，我们可以用相同的方法将最近添加的元素推至队列头部，如此一来队列实际上就是以相反的顺序存储了元素，故而 pop 时从头部 dequeue 即可实现后进先出。

void
push(struct stack_t* stack, int elem)
{
    int i;
    
    enqueue(stack->queue, elem);
    for (i = 1; i < queue; ++i)
        enqueue(stack->queue, dequeue(stack->queue));
}

int
pop(struct stack_t* stack)
{
    return dequeue(stack->queue);
}

时间复杂度（n=栈中元素数量）：第一个版本的栈实现，push()∈Ɵ(enqueue())，pop()∈Ɵ(n*(enqueue()+dequeue()))；第二个版本的栈实现，push()∈Ɵ(n*(enqueue()+dequeue()))，pop()∈Ɵ(dequeue())。可见第一个版本的 push 效率高，pop 效率低，而第二个版本反之。

Ruby 1.9 散列表

Ruby 1.9 有了新的 Hash （散列表）结构和语法。在 1.9 中，你可以用以下方式更快速地写出一个包含以符号为键的元素的 Hash 对象：

#coding: GBK
p ({ 赵天吉: "大刀会", 朱红灯: "义和团" })

输出：

{:赵天吉=>"大刀会", :朱红灯=>"义和团"}

注意这种新的 Hash 字面值只针对于符号键。

结构方面，也有了一个大革命。Hash，顾名思义，一堆杂乱的符号，自然没什么顺序可言，随着我们对 Hash 的了解越深，“Hash 不保证顺序”的概念就越来越深入我们脑海。然而这次，顽皮的 Ruby 又一次颠覆了用户的观念：Hash 也可以是有序的！

在 1.8 中，Hash 对象即是使用分离链接法解决哈希碰撞的散列表。表中每一项需要四个东西：散列码、键的引用、值的引用、下一个散列码相同的元素的引用。为了实现有序的散列表，Ruby 1.9 在表的元素结构体中增加了两个新的指针：指向按顺序排列的前一个和后一个元素的指针，这使得在对散列表进行插入和删除操作时能够维护一个有序的链，实际上就是一个和旧的散列表结构穿插在一起的双向循环链表结构，这两种结构的并集就是新的 Hash 结构了。这个改动的代价是：1.9 的 Hash 的 插入和删除变得更慢了些。这个改动的好处是：Hash 的遍历、迭代、枚举也有序了，它保持了创建 Hash 时元素的先后顺序。同时，因为内部维护着双向循环链表，1.9 遍历 Hash 的速度也比 1.8 快，因为 1.8 必须要遍历整个散列表的桶，自然也就必须经过一些空的桶槽位。

对于为了有序遍历而损失插入、删除的效率是否值得的问题，仁者见仁，智者见智。有些人用散列表来存储一种字典式的结构，然后需要把内容按照有序的方式打印出来，这是常有的；而有些人仅仅是用散列表来进行快速的保存和读取数据。不过我个人倒是有点不赞成直接改动原来的 Hash 类，我们完全可以设计一个新的类，比如 OrderedHash，这样就能让用户有一个选择。

二叉堆

一个最小二叉堆的 C++ 实现，底层采用了数组形式的 Vector 结构存放二叉树。add 添加元素到堆，shift 从堆顶部删除元素，peek 获取堆顶部元素。其中最重要的算法是 bubble-down，它把堆中放置位置过高的“重”（如果是最大堆，自然就是“轻”）物推到了合适位置。二叉堆再抽象一层，就可以用来实现优先队列。

#ifndef _BINARY_HEAP_H_
#define _BINARY_HEAP_H_

#include <vector>

template <typename T>
class BinaryHeap
{
public:
    BinaryHeap()
    {
    }

    BinaryHeap(const T& elem)
    {
        heap_.push_back(elem);
    }

    BinaryHeap(const std::vector<T>& elems)
    {
        heap_= elems;
        for (int i = (heap_.size() - 1) / 2; i >= 0; --i)
            bubbleDown(i);
    }

    virtual void insert(const T& elem)
    {
        int i = heap_.size();
        heap_.resize(i + 1);
        do {
            /* Check heap_[i]'s parent. */
            int j = (i - 1) / 2;
            if (i <= 0 || elem >= heap_[j])
                break;
            heap_[i] = heap_[j];
            i = j;
        } while (true);
        heap_[i] = elem;
    }

    virtual T shift(unsigned idx = 0)
    {
        if (heap_.size() <= idx)
            throw "Heap is empty";
        T ret = heap_[idx];
        heap_[idx] = heap_.back();
        heap_.pop_back();
        bubbleDown(idx);
        return ret;
    }

    virtual const T& peek() const
    {
        return heap_.front();
    }

    virtual BinaryHeap<T>& operator << (const T& elem)
    {
        insert(elem);
        return *this;
    }

    virtual BinaryHeap<T>& operator >> (T& receiver)
    {
        receiver = shift();
        return *this;
    }

protected:
    void bubbleDown(unsigned idx)
    {
        unsigned int max = idx;
        do {
            unsigned int i, j;
            i = idx * 2 + 1;
            j = i + 1;
            /* Pick heap_[i]'s largest child. */
            if (j < heap_.size() && heap_[j] < heap_[max])
                max = j;
            if (i < heap_.size() && heap_[i] < heap_[max])
                max = i;
            if (max == idx)
                break;
            /* Exchange heap_[i] and heap_[max_idx]. */
            T tmp = heap_[idx];
            heap_[idx] = heap_[max];
            heap_[max] = tmp;
            idx = max;
        } while (true);
    }

protected:
    std::vector<T> heap_;
};

#endif /* _BINARY_HEAP_H_ */

同样的算法也用 Ruby 写了一份，但执行效率是有巨大差别的，特别是 Ruby 1.8。不过使用 Ruby 的好处是通过闭包可以方便地传递匿名比较函数，而在 C++ 中则需要传递函数指针，这个过程往往缺乏爱且伴随着痛苦。

class BinaryHeap
  def initialize(*args, &cmptr)
    @cmptr = cmptr
    @heap = args.clone
    i = (@heap.size - 1) >> 1
    while i >= 0
      bubble_down(i)
      i -= 1
    end
  end
  def insert(elem)
    i = @heap.size
    loop do
      j = (i - 1) >> 1
      if j < 0 || @cmptr.call(elem, @heap[j]) <= 0
        @heap[i] = elem
        break
      else
        @heap[i] = @heap[j]
        i = j
      end
    end
    self
  end
  def shift(idx = 0)
    ret = @heap[idx]
    len = @heap.size
    if len > 1
      @heap[idx] = @heap.pop
      bubble_down(idx)
    elsif 1 == len
      @heap.clear
    end
    ret
  end
  def bubble_down(idx)
    len = @heap.size
    loop do
      i = (idx << 1) + 1
      j = i + 1
      max = idx
      max = j if j < len && @cmptr.call(@heap[j], @heap[max]) > 0
      max = i if i < len && @cmptr.call(@heap[i], @heap[max]) > 0
      if max != idx
        @heap[idx],@heap[max] = @heap[max],@heap[idx]
        idx = max
      else
        break
      end
    end
  end
  def to_s(indent = 8)
    helper = lambda do |idx, acc|
      if idx >= @heap.size then ''
      else
        child_base = idx << 1
        helper.call(child_base + 2, acc + 1) +
        ' '*indent*acc + @heap[idx].to_s + "\n" +
        helper.call(child_base + 1, acc + 1)
      end
    end
    helper.call(0, 0)
  end
  def <<(elem)
    add(elem)
  end
end

DATA = 10
data = Array.new(DATA)
DATA.times do |i|
  data[i] = rand(DATA<<1)
end

bh = BinaryHeap.new(*data) { |a, b| a <=> b }
print bh
bh << 1 << 3 << 0 << -3 << 0
print bh
bh.shift
print bh
bh.shift
print bh