对于一组取值范围已知的关键字,如何进行快速插入、删除、获取最值、获取前驱和后继、判断是否存在等操作?红黑树是一个选择,这些操作都要花费O(lgn)的时间复杂度。红黑树没有使用取值范围已知这个性质,直接寻址表倒是使用了取值范围已知这个性质。直接寻址表的插入、删除、判断是否存在的操作只需要常数时间,但是获取前驱和后继需要O(n)的时间。一种解决方案就是将直接寻址和二叉树结合,对于每一个节点,如果子树中存在一个以上的元素,那么置为1,否则置为0:

在给直接寻址表加上一个二叉树之后,获取前驱和后继操作变为O(lgn)时间复杂度。但是为了维护二叉树中的节点性质,插入和删除也需要O(lgn)的时间复杂度。除了二叉树,还有另外一种思路:

在大小为n的数组A上面再加上一个大小为n的数组summary。summary[i]存在关键字,意味着A[in,…,in+n-1]上存在关键字。这个时候,插入、删除、获取前驱、获取后继需要O(n)时间复杂度,相比二叉树,这种方法并没有太大优势。但是,如果形成一种递归的结构,T(n)=T(n)+O(1),时间复杂度就可以变为O(lglgn),这就是vEB的原理。

下图是一个域为[0,16)的vEB树,包含关键字[2,3,5,7,14,15]。

一个vEB树的节点由以下部分构成:

  • 域的大小(u):容纳的关键字的取值范围(0,u],要求u为2的指数。

  • 索引(summary):索引就是vEB(2ceil(log2/2)),如果vEB中存在关键字i,意味着第i的簇中存在一个以上的关键字。

  • 簇(cluster):有2ceil(log2/2)个簇,每一个簇就是vEB(2floor(log2/2))。

  • 最小关键字(min):保存着vEB树中的最小元素,最小元素不位于任何的簇中

  • 最大关键字(max):保存着vEB树中的最大元素。

为了找到簇号和簇中的关键字,需要定义一些操作:

#define NIL			(-1)
#define LOG2(x)		ceil(log2(x))
#define SQRT_C(x)	(1<<static_cast<int>(ceil(LOG2(x)/2)))
#define SQRT_F(x)	(1<<static_cast<int>(floor(LOG2(x)/2)))
#define HIGH(x)		(x/SQRT_F(_u))
#define LOW(x)		(x%SQRT_F(_u))
#define INDEX(x,y)	(x*SQRT_F(_u)+y)
  • HIGH:获取簇号;

  • LOW:获取簇中的关键字;

  • INDEX:从簇号和簇中关键字计算出当前vEB中的关键字。

完整的vEB实现见Gist

节点的定义

和B树一样,节点之间的链接是单向的,所以就可以直接使用智能指针。

class VanEmdeBoas
{
	template <typename T> using vector = std::vector<T>;
	template <typename T> using shared_ptr = std::shared_ptr<T>;
	...
	shared_ptr<VanEmdeBoas> _summary;
	vector<shared_ptr<VanEmdeBoas>> _cluster;
	int _min = NIL, _max = NIL;
	int _u;
}

创建

如果域大于2,需要创建索引和簇数组。

VanEmdeBoas(int u): _u(u)
{
	if (u > 2) {
		_summary = std::make_shared<VanEmdeBoas>(SQRT_C(u));
		_cluster = vector<shared_ptr<VanEmdeBoas>>(SQRT_C(u));
		for (shared_ptr<VanEmdeBoas> &ptr : _cluster)
			ptr = std::make_shared<VanEmdeBoas>(SQRT_F(u));
	}
}

最大值和最小值

最大值和最小值保存在节点中,直接返回即可,只需要常数时间。

int min()
{
	return _min;
}

int max()
{
	return _max;
}

判断包含

如果x是最值,那么直接返回真。如果x不是最值,而当前节点又是vEB(2),那么返回假。如果以上条件都不成立,那么到簇中查找。

bool member(int x)
{
	if (x == _min || x == _max)						// x is the maximum or minimum
		return true;
	else if (_u == 2)								// VEB(2)
		return false;
	return _cluster[HIGH(x)]->member(LOW(x));
}

后继

如果是VEB(2),只有x为0,最大值为1的时候有后继1。如果x小于min,那么min就是x的后继。上述条件不成立,只能到簇中寻找。如果x所在的簇中存在大于x的关键字,那么到簇中寻找后继。否则,从其他簇中寻找后继。

int successor(int x)
{
	if (_u == 2) {									// VEB(2)
		if (x == 0 && _max == 1)
			return 1;
		else
			return NIL;
	} else if (_min != NIL && x < _min) {			// x is less than minimum
		return _min;
	} else {
		int max_low = _cluster[HIGH(x)]->max();
		if (max_low != NIL && LOW(x) < max_low) {	// cluster[HIGGH(x)] has values greater than x
			int offset = _cluster[HIGH(x)]->successor(LOW(x));
			return INDEX(HIGH(x), offset);
		} else {									// cluster[HIGGH(x)] doesn't have values greater than x
			int succ_cluster = _summary->successor(HIGH(x));
			if (succ_cluster == NIL) {
				return NIL;
			} else {
				int offset = _cluster[succ_cluster]->min();
				return INDEX(succ_cluster, offset);
			}
		}
	}
}

前驱

寻找前驱和寻找后继的操作并不是完全对称,因为min是不保存在簇中的。当找遍全部的簇,没有找到前驱,那么min很可能就是前驱。

int predecessor(int x)
{
	if (_u == 2) {									// VEB(2)
		if (x == 1 && _min == 0)
			return 0;
		else
			return NIL;
	} else if (_max != NIL && _max < x) {			// x is greater than maximum
		return _max;
	} else {
		int min_low = _cluster[HIGH(x)]->min();
		if (min_low != NIL && min_low < LOW(x)) {	// cluster[HIGGH(x)] has values less than x
			int offset = _cluster[HIGH(x)]->predecessor(LOW(x));
			return INDEX(HIGH(x), offset);
		} else {									// cluster[HIGGH(x)] doesn't have values less than x
			int pred_cluster = _summary->predecessor(HIGH(x));
			if (pred_cluster == NIL) {
				if (_min != NIL && x > _min)		// minimum is less than x
					return _min;
				return NIL;
			} else {
				int offset = _cluster[pred_cluster]->max();
				return INDEX(pred_cluster, offset);
			}
		}
	}
}

插入

如果是一个空的vEB,将min和max设置为插入元素即可。如果非空,那么首先与min比较,如果x小于min,那么交换x和min,插入原来的min关键字。如果当前的vEB的域大于2,那么需要把元素插入簇中,如果原来的簇是空的,还需要更新索引。最后,更新最大关键字max。

#define INSERT_EMPTY(ptr, x)	do { ptr->_max = ptr->_min = x; } while (0)

void insert(int x)
{
	if (_min == NIL) {								// vEB has no member
		INSERT_EMPTY(this, x);
	} else {
		if (x < _min)								// x is less than minimum
			std::swap(x, _min);
		if (_u > 2)
			if (_cluster[HIGH(x)]->min() == NIL) {
				_summary->insert(HIGH(x));
				INSERT_EMPTY(_cluster[HIGH(x)], LOW(x));
			} else {
				_cluster[HIGH(x)]->insert(LOW(x));
			}
		if (x > _max)								// update maximum
			_max = x;
	}
}

删除

如果vEB中只有一个关键字,那么将min和max都置为NIL即可。如果是vEB(2)并且包含两个关键字,那么将min和max置为留下的关键字。如果vEB既不是只有一个关键字,又不是vEB(2),那就需要从簇中删除关键字了。 如果要删除的关键字刚好是最小元素,那么将位于簇中的关键字取出代替原来的最小关键字,然后递归地在簇中删除最小关键字。删除操作可能会导致某个簇变为空,那么就需要修改索引,在索引中删除这个簇的编号。 删除的关键字可能刚好是max,这个时候需要更新max。如果删除关键字后的簇不为空,那么把这个簇中的最大关键字作为max,否则就需要从其他簇中找到max。

void remove(int x)
{
	if (_min == _max && _max == x) {			// vEB has noly one member
		_min = _max = NIL;
	} else if (_u == 2) {						// vEB(2)
		_max = _min = x == 0;
	} else {									// x is the minimum
		if (x == _min) {
			int first_cluster = _summary->min();
			x = INDEX(first_cluster, _cluster[first_cluster]->min());
			_min = x;
		}
		_cluster[HIGH(x)]->remove(LOW(x));
		if (_cluster[HIGH(x)]->min() == NIL) {	// cluster[HIGH(x)] be empty
			_summary->remove(HIGH(x));
			if (x == _max) {
				int summary_max = _summary->max();
				if (summary_max == NIL)
					_max = _min;
				else 
					_max = INDEX(summary_max, _cluster[summary_max]->max());
			}
		} else if (x == _max) {					
			_max = INDEX(HIGH(x), _cluster[HIGH(x)]->max());
		}
	}
}