C++ 的 AVL 二叉树

• 下载源代码和演示项目 - 194.6 KB

引言

我经常需要一个提供快速插入和快速索引的容器。我也经常需要排序的容器。在这里，我提供了一个 AVL 二叉树的实现，它可以满足所有这些需求。

背景

• 以下是一些关于 AVL 二叉树的信息：AVL 树
• 这是 CodeProject 上的另一个关于 AVL 二叉树的条目（我没有使用这个实现）
  • Addison-Velski 和 Landis (AVL) 二叉树
• 这是 CodeProject 上讨论 Chen Venkataraman 的 HighResElapsedTimer 的条目，我在示例程序中使用它
  • 高分辨率计时器

Using the Code

您可以将 HeightBalancedTree<> 模板用作一个序列容器，支持对对象进行快速的任意插入和删除，或者用作一个排序容器。

如果您将树用作快速序列容器，请使用方法 InsertByIndex、FindByIndex 和 RemoveByIndex。

如果您将树用作排序容器，请使用方法 InsertComparable、FindComparable 和 RemoveComparable。这些方法使用用户提供的 Comparator 类型来比较容器中存储的对象。

您始终可以使用重载的 operator[]，它的工作方式与 FindByIndex 相同。如果索引无效，它会抛出 std::out_of_range 异常。

容器的所有按索引修改和访问方法大约需要 O(log(n)) 时间。

容器的所有按比较修改和访问方法大约需要 O(k * log(n)) 时间，其中 k 是比较任何两个对象所需的时间。

这里有一些示例代码，用于创建一个并修改一个 size_t 的随机访问数组

typedef HeightBalancedTree<size_t> SizeTTree;
SizeTTree tree;
for (size_t i = 0; i < n; ++i)
{
    tree.InsertByIndex(indices[i], data[i]);
}
for (size_t i = 0; i < n; ++i)
{
    tree.RemoveByIndex(0);
}

这里有一些示例代码，用于创建一个并修改一个 string 的排序序列

#ifdef UNICODE
    std::wostream & tcout = wcout;
    typedef HeightBalancedTree<
        std::basic_string<wchar_t>,
        StringComparator<
            std::basic_string<wchar_t>
        >
    > TStringTree;
#else
    std::ostream & tcout = cout;
    typedef HeightBalancedTree<
        std::string,
        StringComparator<std::string>
    > TStringTree;
#endif

TStringTree tree;
tree.InsertComparable(TEXT("ABE"));
tree.InsertComparable(TEXT("aBdE"));
tree.InsertComparable(TEXT("AbCd"));
tree.InsertComparable(TEXT("aBc"));
tree.InsertComparable(TEXT("AbD"));
tree.InsertComparable(TEXT("aBe"));
for (size_t i = 0; i < tree.Size(); ++i)
{
    tcout << "tree[" << i << "] = 
                  " << tree[i] << endl;
}

关注点

请告诉我您对这个的看法。我很乐意听取建议。

历史

• 2005 年 12 月 14 日 - 1.0.1 修复了 FindComparable 中的一个错误：返回的索引不正确
• 2005 年 12 月 13 日 - 初始版本上传到 CodeProject

许可证

本文未附加明确的许可证，但可能在文章文本或下载文件本身中包含使用条款。如有疑问，请通过下面的讨论区联系作者。

作者可能使用的许可证列表可以在此处找到。