About
RSS

Bit Focus


万能巧械 - 二叉检索树 [零]

Posted at 2012-01-23 05:04:23 | Updated at 2024-12-09 16:52:53

    在维护固定的顺序统计量有先天优势, 但在面对如下需求的时候又极其手短
    前两个手短指的是时间复杂度, 要完成这些功能, 跟直接到未排序数组里面去暴力解决是一回事. 而后面一个则是堆的硬伤. 严格来说, 堆并不是一种数据结构, 说穿了堆只有数据而没有结构 (是的, 即使是数组也是数据结构, 因此严格来讲应该说成, 它没有自身独特的结构, 还记得 STL 中优先队列的模板定义吧, 它的底层存储结构是可以通过模板参数替换的), 其精髓在于算法. 由于不具备结构, 也就是说没有实质上的数据与数据的关系, 因而不方便弄出多个不同的键. 这个现在空谈就像白切鸡一样没什么味道, 以后有机会再加上油盐详述.

    较之堆更加全能的索引数据结构非二叉检索树 (binary search tree, 缩写为 BST) 莫属了, 一般的二叉检索树可以很轻松地解决按键索引, 而若将子树节点计数器加诸其上, 就能进行快速的随机索引. 不过, 在这篇文章中, 只讨论理想状态下的二叉树, 不考虑那种被精心准备的数据叉成链表的情况.

    首先还是把二叉树的架子给搭出来
template <typename T>
class binary_search_tree {
    struct node {
        T t;
        node* left;
        node* right;
        int load;

        explicit node(T const& rhs)
            : t(rhs)
            , left(NULL)
            , right(NULL)
            , load(1)
        {}
    };

    node* root;

    typedef typename T::key_type key_type;
public:
    binary_search_tree()
        : root(NULL)
    {}
public:
    void insert(T const& e);

    void remove_by(typename T::key_type const& key);
    void remove_at(int position);

    T& element_by(typename T::key_type const& key);
    T& element_at(int position);
};
    简单起见, 这里只有类似 T& element_by(typename T::key_type const& key); 的接口, 而没有文艺地给出对应的 const 版本, 如 T const& element_by(typename T::key_type const& key) const;. 只是为了说明其中的处理方式而已, 不追求工程上的尽善尽美.
    这里就能看到一点结构上的东西了, 从内部 struct node 的定义, 二叉树至少得来两个叉, 也就是指向左子节点的指针 left 跟指向右子节点的指针 right. 除此之外就是之前提到的, 节点负载计数器 load. 而且这个结构对类型 T 是有要求的, 它必须具备复制构造函数, 并且需要定义内部类型 key_type; 另外, 有代码中没有体现出来的约定, T 类型的实例应具有取得键的方法 key(), 而键用于进行小于比较.

    相比于普通二叉树, 任何时候, 二叉检索树中的节点按照树的中序遍历结果将是有序的. 换句话说, 任一个节点中的元素比左子树中任何节点中的元素都要大, 而比右子树中任何节点中的元素要小. 这是二叉检索树神奇功能的力量来源. 只要有这个特性, 按键索引就像斧头剁茄子一样是非常简单的事情.

                +---+
                | d |---( < )-.
                +---+         :
       .-------'   : `---.    :
    +---+          :    +---+ :
    | b |  .-( < )-'    | e |-'
    +---+  :            +---+
   /     \ :                 \
+---+   +---+                 +---+
| a |   | c |                 | f |
+---+   +---+                 +---+

    对 element_by 函数的实现思路很简单, 如果给定的节点的键值比参数键值大, 那么要寻找的元素在左子树中; 若参数键值较大, 则要去右子树寻找元素. 否则, 当前节点中的元素就是要寻找的元素. 那么实现如下
T& element_by(key_type const& key)
{
    return element_by_from(key, root)->t;
}

static node* element_by_from(key_type const& key, node* parent)
{
    if (key < parent->t.key()) {
        return element_by_from(key, parent->left);
    }
    if (parent->t.key() < key) {
        return element_by_from(key, parent->right);
    }
    return parent;
}
    其中 static 表示 element_by_from 是类的静态函数. 上述两个函数均在 class binary_search_tree 空间中. 不考虑找不到节点的情况.

    随机索引依附的力量, 则是检索树的另一个性质, 任何时候, 一个节点的负载量等于左子树的负载量与右子树的负载量之和再加 1, 如果某一子树为空, 则该子树的负载量按零计.

        +---+
        | 6 |
        +---+
       /     \
    +---+   +---+
    | 3 |   | 2 |
    +---+   +---+
   /     \       \
+---+   +---+   +---+
| 1 |   | 1 |   | 1 |
+---+   +---+   +---+

    这样一来, 给定一个位置值, 如果该位置值恰好等于 (元素位置从 0 开始) 左子树的负载量, 那么当前节点中的元素就是要找的元素; 若位置值较小于左子树负载量, 则在左子树中去寻找; 否则, 到右子树中寻找. 最后一种情况中, 需要将位置值减去左子树和当前节点的总节点数. 实现如下
T& element_at(int position)
{
    return element_at_from(position, root)->t;
}

static node* element_at_from(int position, node* parent)
{
    int left_load = (NULL == parent->left) ? 0 : parent->left->load;
    if (position < left_load) {
        return element_at_from(position, parent->left);
    }
    if (left_load < position) {
        position = position - left_load - 1; // adjust position
        return element_at_from(position, parent->right);
    }
    return parent;
}
    同样这两个函数均在 class binary_search_tree 空间中.

    相较之查找函数, insertremove_* 都会修改树的结构, 需要维护树的上述性质 --- 键序和负载计数.
    对于 insert 函数而言, 维护上述性质意味着两件事情, 一是找到键序上合理的位置, 另外就是在实际插入之后要更新被插入的节点到根节点这条路径上每个节点的负载. 前一性质维护与按键检索过程非常相似, 而后一性质维护, 在没有异常发生的前提下, 等价于在查找插入位置的过程中更新节点负载. 因此可以如下实现插入函数
void insert(T const& e)
{
    insert_at(e, &root);
}

static void insert_at(T const& e, node** slot)
{
    if (NULL == *slot) {
        *slot = new node(e);
        return;
    }
    ++((*slot)->load);
    if (e.key() < (*slot)->t.key()) {
        insert_at(e, &((*slot)->left));
        return;
    }
    insert_at(e, &((*slot)->right));
}
    这两个函数均在 class binary_search_tree 空间中.

    现在可以写一小段程序验证一下了
#include <string>
#include <iostream>

struct data {
    typedef int key_type;
    key_type _key;
    std::string value;

    data(int k, std::string v)
        : _key(k)
        , value(v)
    {}

    data()
        : _key(0)
    {}

    key_type key() const
    {
        return _key;
    }
};

int main()
{
    binary_search_tree<data> tree;
    tree.insert(data(5, "naganohara"));
    tree.insert(data(4, "aioi"));
    tree.insert(data(5, "minakami"));
    tree.insert(data(3, "sinonome"));
    tree.insert(data(7, "hakase"));
    tree.insert(data(6, "sakamoto"));
    for (int i = 0; i < 6; ++i) {
        data& d = tree.element_at(i);
        std::cout << d.key() << ':' << d.value << std::endl;
    }
    std::cout << std::endl;
    std::cout << tree.element_by(3).value << std::endl;
    std::cout << tree.element_by(4).value << std::endl;
    std::cout << tree.element_by(5).value << std::endl;
    std::cout << tree.element_by(6).value << std::endl;
    std::cout << tree.element_by(7).value << std::endl;
    return 0;
}
    爬树容易下树难, 相比于插入和检索, 删除节点的情况会稍多一些. 请猛戳这里继续下文.

Post tags:   C++  Generic Programming  Data Structure  Binary Search Tree  Algorithm  Order Statistic  Template

Leave a comment:




Creative Commons License Your comment will be licensed under
CC-NC-ND 3.0


. Back to Bit Focus
NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
About this site