自制radix_tree

介绍

前缀树

radix tree,中文基数树,是用来解决hash冲突和hash表的设计,前缀树是一种有序树,
用于保存关联数组,键一般都为字符串.每个节点的所有子孙都有相同的前缀.最后所有的叶子节点保存了要存储的元素.
前缀树经常用于搜索提示,比如输入一个网址,可以自动搜索出可能的选择.前缀树的问题在于可能过于稀疏,空间浪费严重.比如几个字符串有相同某段前缀,但是如果按每个字符来分的话,会出现很多没有用的节点.

前缀压缩树

为了解决问题,出现了压缩前缀树,对于基数树的每个节点,如果该节点是唯一的儿子的话,就和父节点合并.
下面就来自己实现一个基数树容器.

组件

首先,是一颗树,就必须有节点类的定义,radix_tree_node,其次,既然是容器,我们需要一个迭代器的类,最后是radix_tree本身.

节点

第一,节点要存什么,节点要存的信息有键和要存的元素,我们可以用一个pair来实现,其次,节点要有子节点,由于子节点数量不确定,我们可以用map来存,如果用线性表来存访问速度就会是O(n).为了方便还存了父节点和键.
声明代码如下:

template <typename K, typename T>
class radix_tree_node {
    friend class radix_tree<K, T>;
    friend class radix_tree_it<K, T>;

    typedef std::pair<const K, T> value_type;
    typedef typename std::map<K, radix_tree_node<K, T>* >::iterator it_child;

private:
//构造和析构
    radix_tree_node() : m_children(), m_parent(NULL), m_value(NULL), m_depth(0), m_is_leaf(false), m_key() { }
    radix_tree_node(const value_type &val);

    ~radix_tree_node();
//类成员
    std::map<K, radix_tree_node<K, T>*> m_children;
    radix_tree_node<K, T> *m_parent;
    value_type *m_value;
    int m_depth;
    bool m_is_leaf;
    K m_key;
};

重载析构

在初始化对象的时候，根据参数的不同，使用不同的构造函数，这里我们写了重载构造函数和删除对象时的析构函数：

template <typename K, typename T>
radix_tree_node<K, T>::radix_tree_node(const value_type &val) :
    m_children(),
    m_parent(NULL),
    m_value(NULL),
    m_depth(0),
    m_is_leaf(false),
    m_key()
{
    m_value = new value_type(val);
}

template <typename K, typename T>
radix_tree_node<K, T>::~radix_tree_node()
{
    it_child it;
    for (it = m_children.begin(); it != m_children.end(); ++it) {
        delete it->second;
    }
    delete m_value;
}

要注意释放申请的内存

迭代器

我们要定义树的迭代器,首先迭代器能访问树节点上保存的信息(键值),不能访问其他信息,自己定义的迭代器最好继承标准库迭代器std::iterator:

template <typename K, typename T>
//要继承的iterator实例化参数要加std::forward_iterator_tag,因为树是向前迭代器
class radix_tree_it : public std::iterator<std::forward_iterator_tag, std::pair<K, T> > {
    friend class radix_tree<K, T>;

public:
    radix_tree_it() : m_pointee(0) { }
    radix_tree_it(const radix_tree_it& r) : m_pointee(r.m_pointee) { }
    radix_tree_it& operator=(const radix_tree_it& r) { m_pointee = r.m_pointee; return *this; }
    ~radix_tree_it() { }

    std::pair<const K, T>& operator*  () const;
    std::pair<const K, T>* operator-> () const;
    const radix_tree_it<K, T>& operator++ ();
    radix_tree_it<K, T> operator++ (int);
    // const radix_tree_it<K, T>& operator-- ();
    bool operator!= (const radix_tree_it<K, T> &lhs) const;
    bool operator== (const radix_tree_it<K, T> &lhs) const;

private:
    radix_tree_node<K, T> *m_pointee;
    radix_tree_it(radix_tree_node<K, T> *p) : m_pointee(p) { }

    radix_tree_node<K, T>* increment(radix_tree_node<K, T>* node) const;
    radix_tree_node<K, T>* descend(radix_tree_node<K, T>* node) const;
};

我们重载了一些操作符,接下来看如何实现

操作符

template <typename K, typename T>
std::pair<const K, T>& radix_tree_it<K, T>::operator* () const
{
    return *m_pointee->m_value;
}

template <typename K, typename T>
std::pair<const K, T>* radix_tree_it<K, T>::operator-> () const
{
    return m_pointee->m_value;
}

template <typename K, typename T>
bool radix_tree_it<K, T>::operator!= (const radix_tree_it<K, T> &lhs) const
{
    return m_pointee != lhs.m_pointee;
}

template <typename K, typename T>
bool radix_tree_it<K, T>::operator== (const radix_tree_it<K, T> &lhs) const
{
    return m_pointee == lhs.m_pointee;
}

template <typename K, typename T>
const radix_tree_it<K, T>& radix_tree_it<K, T>::operator++ ()
{
    if (m_pointee != NULL)
        m_pointee = increment(m_pointee);
    return *this;
}

template <typename K, typename T>
radix_tree_it<K, T> radix_tree_it<K, T>::operator++ (int)
{
    radix_tree_it<K, T> copy(*this);
    ++(*this);
    return copy;
}

实现increment和descend

关键在于如何遍历树的叶子节点,从一个叶子节点要寻找的下一个节点要么是自己的下一个兄弟节点,需要通过父节点来访问到,要么自己已经是最后一个兄弟节点,这时候需要找父节点的下一个兄弟节点,再往下找到叶子节点

template <typename K, typename T>
radix_tree_node<K, T>* radix_tree_it<K, T>::increment(radix_tree_node<K, T>* node) const
{
    radix_tree_node<K, T>* parent = node->m_parent;

    if (parent == NULL)
        return NULL;

    typename radix_tree_node<K, T>::it_child it = parent->m_children.find(node->m_key);
    assert(it != parent->m_children.end());
    ++it;

    if (it == parent->m_children.end())
        return increment(parent);
    else
        return descend(it->second);
}

template <typename K, typename T>
radix_tree_node<K, T>* radix_tree_it<K, T>::descend(radix_tree_node<K, T>* node) const
{
    if (node->m_is_leaf)
        return node;

    typename radix_tree_node<K, T>::it_child it = node->m_children.begin();

    assert(it != node->m_children.end());

    return descend(it->second);
}

接下来要实现radix_tree,也是核心部分.

radix_tree

赏

谢谢你请我吃糖果