- 按键索引 - 给定一个元素的键, 在数据集合中找到与该键相同 (或较小, 较大) 的元素
- 随机索引 - 在堆建立时, 可以给定一个固定的数值 K, 让堆维护第 K 大的元素, 但毕竟这个 K 是建堆时固定的
- 多键索引 - 堆中的元素的排序索引是唯一的, 如果想要其它的索引, 则需要借助额外的数据结构
较之堆更加全能的索引数据结构非二叉检索树 (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 |
+---+ +---+ +---+
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 空间中.相较之查找函数,
insert 与 remove_* 都会修改树的结构, 需要维护树的上述性质 --- 键序和负载计数.对于
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;
}
