C++ AVL 树模板
4.67/5 (12投票s)
一个 C++ AVL 树模板。
引言
本文档解释了如何使用 avl_tree 模板。Adelson-Velskii 和 Landis 平衡二叉搜索树（或 AVL 树）在许多关于基本数据结构的好书中都有描述。我能找到的关于该主题的最佳网页是“一个 Visual Basic AVL 树容器类”。
本文档以及其描述的源代码都属于公共领域。
为避免本文档（及源代码注释）中使用术语可能引起的混淆，此处是对 AVL 树的总结性描述。AVL 树是一组节点（或元素）。每个节点都与一个唯一的键值相关联。键值可以按从小到大的顺序排列。树中的每个节点可以（也可能不）有一个左子节点，也可以（也可能不）有一个右子节点。如果节点 A 是节点 B 的子节点，那么 B 是 A 的父节点。如果 A 是 B 的左子节点，A 的键必须小于 B 的键。同样，如果 A 是 B 的右子节点，A 的键必须大于 B 的键。树中的所有节点都有且只有一个父节点，根节点除外，根节点没有父节点。如果 C 是 A 的父节点，或者 A 的父节点是 C 的后代，那么节点 A 是节点 C 的后代。如果一个节点不是整个树的根，那么它就是由该节点及其所有后代组成的子树的根。节点的左子树是根节点为该节点左子节点的子树。节点的右子树是根节点为该节点右子节点的子树。节点深度比其父节点的深度多一。根节点的深度为 1。树的深度是最大节点深度。节点的平衡因子是其右子树的深度减去其左子树的深度，不存在的子树的深度视为 0。在 AVL 树中，任何节点的平衡因子只能是 -1、0 或 1。
市面上有几种开源的 C 和 C++ AVL 树实现（参见 C/C++ 用户组页面的“热门链接”，然后是“数据结构”）。但据我所知，这是唯一一个不使用具体指针而是通过抽象“句柄”来操作树节点的实现。如果所有节点都在一个数组中，您可以使用节点索引作为句柄而不是节点指针。这种方法可以在内存紧张时压缩节点的大小。索引句柄可以使树持久化变得简单，只需一次磁盘写入即可输出节点数组，一次磁盘读取即可读回。该模板还允许树存储在辅助存储中，节点会被“分页”进出内存。
为了达到所需的抽象级别，avl_tree 模板使用了大量简短的内联函数。因此，当使用该模板时，函数内联可以显著提高性能。如果使用 GNU GCC 级别的 1 优化（-O 选项）编译测试套件 (test_avl.cpp)，其执行速度是未优化编译（默认）时的两倍。
模板代码不使用递归。该实现通常对堆栈友好，除了 iter 类可能例外。iter 类的实例包含一个句柄数组，其维度是最大树深度减一。由于键比较可能很复杂，代码避免了对同一对节点键值进行重复比较。为避免混乱，默认析构函数未在此处记录。
源文件
- 模板的源代码位于头文件 avl_tree.h 中
- 模板的测试套件位于文件 test_avl.cpp 中
- avl_ex1.cpp 展示了一个使用指针作为句柄的模板实例化示例
- avl_ex2.cpp 展示了一个使用数组索引作为句柄的模板实例化示例
所有这些代码都可以使用当前版本的 GNU GCC 和 Visual C++ .NET 进行编译。
引用类
为了描述模板类/类型参数的约束，或模板类参数的成员类型的约束，我喜欢使用引用类。这不一定意味着被约束的类型必须使用引用类作为其定义。只需要确保对引用类的任何使用或其某个实例的任何使用，也都是对被约束类型或其某个实例的可能使用。当使用带有 ANY_ 前缀的标识符时，这意味着该标识符的所有出现都应替换为相同的类型（或隐式转换为该类型的类型）。以函数模板为例
template <class A>
void foo(A &a) { a.x(a.y()); }
参数 A 的引用类将是
class A
{
public:
void x(ANY_px p);
ANY_px y(void);
};
以下类可以作为类 A 参数传递给模板
struct someA
{
public:
static double x(int aintp);
signed char y(bool f = true) const;
};
由于引用类中 x() 的返回类型是 void，因此它可以返回任何类型（或为 void）在实际参数类中。y() 可以返回 signed char，因为 signed char 可以隐式转换为 int。成员函数可以声明为 static 或 const，因为这使得函数的使用更加灵活，而非不灵活。
命名空间
avl_tree 模板位于 abstract_container 命名空间中。AVL 树头文件也定义了这个枚举类型
enum search_type
{
EQUAL = 1,
LESS = 2,
GREATER = 4,
LESS_EQUAL = EQUAL | LESS,
GREATER_EQUAL = EQUAL | GREATER
};
在 abstract_container 命名空间中。
模板参数
avl_tree 模板以以下内容开始
template <class abstractor, unsigned max_depth = 32>
class avl_tree . . .
抽象器模板参数的引用类的成员
引用类的所有成员都是 public 的。
类型 handle
每个节点必须与一个节点句柄相关联，这是句柄类型的一个唯一值。以下是句柄的引用类
class handle
{
public:
// No default value for handles is assumed by the template.
handle(void);
handle(handle &h);
void operator = (handle &h);
bool operator == (handle &h);
};
类型 key
每个节点必须与一个 key 相关联，这是 key 类型的一个唯一值。key 和 handle 之间的区别在于，可以使用 handle 方便地“查找”节点，但不能方便地使用 key 来查找。事实上，这个模板的重点就是方便地根据 key 查找节点。以下是 key 的引用类
classkey
{
public:
//Only have to copy it
key(key&k);
};
类型 size
size 类型是 char、short、int 或 long，signed 或 unsigned。它必须足够大，能够容纳树中可能的最大节点数。
函数 get_less, get_greater
handle get_less(handle h, bool access = true);
handle get_greater(handle h, bool access = true);
返回句柄为 h 的节点的左/右子节点的句柄。如果 access 为 true，并且子节点存储在辅助存储中，则必须将其读入内存。如果 access 为 false，则子节点不必读入内存。如果您的实例化不使用辅助存储，则忽略 access 参数。
函数 set_less, set_greater
void set_less(handle h, handle lh);
void set_greater(handle h, handle gh);
给定节点句柄 h，设置该节点的左/右子节点的句柄。
函数 get_balance_factor
int get_balance_factor(handle h);
返回句柄为 h 的节点的平衡因子。
函数 set_balance_factor
void set_balance_factor(handle h, int bf);
设置句柄为 h 的节点的平衡因子。唯一可能的平衡因子值是 -1、0 和 1。
函数 compare_key_node
int compare_key_node(key k, handle h);
比较一个 key 和一个 node 的 key。如果 key 小于节点的 key，则返回负值。如果 key 等于节点的 key，则返回零。如果 key 大于节点的 key，则返回正值。
函数 compare_node_node
int compare_node_node(handle h1, handle h2);
比较两个节点的键。如果第一个节点的 key 小于第二个节点的 key，则返回负值。如果第一个节点的 key 等于第二个节点的 key，则返回零。如果第一个节点的 key 大于第二个节点的 key，则返回正值。
函数 null
handle null(void);
始终返回相同、无效的句柄值，该值称为 null 值。
函数 read_error
bool read_error(void);
如果读取辅助存储时发生错误，则返回 true。如果您的模板实例化不使用辅助存储，则使用此定义
bool read_error(void) { return(false); }
无参构造函数
abstractor(void);
max_depth
这是实例化类的实例的最大树深度。您几乎肯定希望根据任何给定时间可能存在于树实例中的最大节点数来选择最大深度。为此，设最大深度为 M，使得
MN(M)<= 最大节点数 <MN(M + 1)
其中 MN(d) 表示深度为 d 的 AVL 树中的最小节点数。以下是从 2 到 45 的 d 的 MN(d) 值表。
| D | MN(d) |
| 2 | 2 |
| 3 | 4 |
| 4 | 7 |
| 5 | 12 |
| 6 | 20 |
| 7 | 33 |
| 8 | 54 |
| 9 | 88 |
| 10 | 143 |
| 11 | 232 |
| 12 | 376 |
| 13 | 609 |
| 14 | 986 |
| 15 | 1,596 |
| 16 | 2,583 |
| 17 | 4,180 |
| 18 | 6,764 |
| 19 | 10,945 |
| 20 | 17,710 |
| 21 | 28,656 |
| 22 | 46,367 |
| 23 | 75,024 |
| 24 | 121,392 |
| 25 | 196,417 |
| 26 | 317,810 |
| 27 | 514,228 |
| 28 | 832,039 |
| 29 | 1,346,268 |
| 30 | 2,178,308 |
| 31 | 3,524,577 |
| 32 | 5,702,886 |
| 33 | 9,227,464 |
| 34 | 14,930,351 |
| 35 | 24,157,816 |
| 36 | 39,088,168 |
| 37 | 63,245,985 |
| 38 | 102,334,154 |
| 39 | 165,580,140 |
| 40 | 267,914,295 |
| 41 | 433,494,436 |
| 42 | 701,408,732 |
| 43 | 1,134,903,169 |
| 44 | 1,836,311,902 |
| 45 | 2,971,215,072 |
如果在特定实例化中，树实例的最大节点数为 1,000,000，则最大深度应为 28。选择 28 是因为 MN(28) 为 832,039，小于或等于 1,000,000，而 MN(29) 为 1,346,268，严格大于 1,000,000。
如果您插入的节点会导致树的深度超过您指定的最大深度，则结果是未定义的。
max_depth 值每增加 1，iter 类实例的大小就会增加 sizeof(handle)。max_depth 的唯一其他用途是作为代码中各处使用的位数组的大小。通常，位数组的字节数是大小向上舍入为 int 中位数目的倍数，然后除以字节中位数。所有这些都是一种迂回的说法，即如果您不使用 iter 实例，您可以毫无顾忌地为 max_depth 值添加一个大的安全裕度。
公共成员
类型 handle
与抽象器参数类的 handle 类型成员相同。
类型 key
与抽象器参数类的 key 类型成员相同。
类型 size
与抽象器参数类的 size 类型成员相同。
函数 insert
handle insert(handle h);
将具有给定句柄的节点插入到树中。该节点必须与一个键值相关联。节点左/右子节点句柄及其平衡因子的初始值是无关紧要的。如果成功，此函数将返回插入节点的句柄。如果待插入的节点具有与树中已存在的节点相同的键值，则不执行插入，并返回树中已存在节点的句柄。如果读取辅助存储时发生错误，则返回 null 值。调用此函数会使所有当前存在的 iter 类实例（正在遍历此树的实例）失效。
函数 search
handle search(key k, search_type st = EQUAL);
搜索树中的特定节点，如果找到节点则返回其 handle，如果未找到节点则返回 null 值。待搜索的节点取决于 st 参数的值。
| st 的值 | 待搜索的节点 |
EQUAL | 键值为 k 的节点。 |
LESS | 键小于 key k 的所有节点中，键值最大的节点。 |
GREATER | 键大于 key k 的所有节点中，键值最小的节点。 |
LESS_EQUAL | 键小于或等于 key k 的所有节点中，键值最大的节点。 |
GREATER_EQUAL | 键大于或等于 key k 的所有节点中，键值最小的节点。 |
函数 search_least
handle search_least(void);
返回树中键值最小的节点的句柄。如果树为空或从辅助存储读取时发生错误，则返回 null 值。
函数 search_greatest
handle search_greatest(void);
返回树中键值最大的节点的句柄。如果树为空或从辅助存储读取时发生错误，则返回 null 值。
函数 remove
handle remove(key k);
从树中移除具有给定 k 的节点。返回被移除节点的句柄。如果树中没有具有给定键的节点，或者从辅助存储读取时发生错误，则返回 null 值。调用此函数会使所有当前存在的 iter 类实例（正在遍历此树的实例）失效。
函数 purge
void purge(void);
移除树中的所有节点，使其变为空。
函数 is_empty
bool is_empty(void);
如果树为空，则返回 true。
函数 read_error
void read_error(void);
如果从辅助存储读取树节点时发生错误，则返回 true。发生读取错误时，树的状态是未定义的。
无参构造函数
avl_tree(void);
将树初始化为空状态。
函数模板 build
template<typename fwd_iter>
bool build(fwd_iter p, size num_nodes);
从按 key 值升序排序的节点序列构建一棵树。序列中的节点数由 num_nodes 指定。p 是一个前向迭代器，最初指向序列中的第一个节点。以下是 fwd_iter 的引用类
class fwd_iter
{
public:
fwd_iter(fwd_iter &);
handle operator * (void);
void operator ++ (int);
};
此函数调用前树中的任何节点都会被清除。当迭代器指向序列中的最后一个节点时，它将最后一次递增。如果构建树时发生读取错误，build() 将返回 false。此函数的 time complexity 为 O(n x log n)，但它比逐个插入序列中的节点更有效，并且生成的树通常具有更好的平衡性。
复制构造函数和赋值运算符？
如果抽象器类具有复制构造函数和赋值运算符，则 avl_tree 实例化将具有（默认的）复制构造函数和赋值运算符。
类 iter
此成员类的实例是树中按键升序排序的节点序列的双向迭代器。本节的子节描述了 iter 的 public 成员。
-
无参构造函数
iter(void);
将迭代器初始化为
null状态。 -
函数 start_iter
void start_iter(avl_tree &tree, key k, search_type st = EQUAL);
使迭代器指向树中由第一个参数指定的节点。如果树中找不到特定节点，或发生读取错误，则将迭代器置于
null状态。由st参数确定要指向的特定节点。st 的值 待搜索的节点 EQUAL键值为 k的节点。LESS键小于 key k的所有节点中，键值最大的节点。GREATER键大于 key k的所有节点中，键值最小的节点。LESS_EQUAL键小于或等于 key k的所有节点中，键值最大的节点。GREATER_EQUAL键大于或等于 key k的所有节点中，键值最小的节点。 -
函数 start_iter_least
void start_iter_least(avl_tree &tree);
使迭代器指向给定树中
key最小的节点。如果树为空或发生读取错误，则将迭代器置于null状态。 -
函数 start_iter_greatest
void start_iter_greatest(avl_tree &tree);
使迭代器指向给定树中
key最大的节点。如果树为空或发生读取错误，则将迭代器置于null状态。 -
运算符 *
handle operator * (void);
返回迭代器指向的节点的句柄。如果迭代器处于
null状态，则返回null值。 -
前缀和后缀运算符 ++
void operator ++ (void); void operator ++ (int);
使迭代器指向的节点的
key大于迭代器当前指向的节点的key。如果当前指向的节点的key是树中所有节点key的最大值，或者发生读取错误，则将迭代器置于null状态。如果迭代器已处于null状态，则不起作用。 -
前缀和后缀运算符 --
void operator -- (void); void operator -- (int);
使迭代器指向的节点的
key小于迭代器当前指向的节点的key。如果当前指向的节点的key是树中所有节点key的最小值，或者发生读取错误，则将迭代器置于null状态。如果迭代器已处于null状态，则不起作用。 -
函数 read_error
如果发生读取错误，则返回
true。 -
默认复制构造函数和赋值运算符
这些成员函数存在且可以使用。
保护成员
变量 abs
abstractor abs;
变量 root
handle root;
包含 AVL 树根节点的句柄。如果树为空，则包含 null 值。
其他保护成员
其他 protected 成员最容易通过阅读源代码来理解。
历史
- 2002 年 9 月 12 日 - 修复了处理树节点在辅助存储中发生错误的一些问题