Addison-Velski 和 Landis (AVL) 二叉树

下载演示项目 - 54 Kb

我实现了 Addison-Velski 和 Landis 的二叉树 (AVL 树)，它允许在对数时间内执行标准的插入、搜索和删除操作。普通的二叉树可能会变得非常模糊。它们可能会变成线性结构，基本操作需要线性时间而不是对数时间。AVL 树的优势在于插入和删除操作后重构树的策略。重构操作本身只需要对数时间。因此，这些树是存储大量项目的非常高效的二叉树。我使用这种树来排序数据。使用 AVL 树排序数据需要 n*log(n) 时间，因此您可以以最佳时间排序大量数据。我使用该技术在四分之一小时内对数十万个项目进行了排序。很容易消除重复项，重复项将不会被插入到树中。还有哪个算法能如此高效地工作？而且最大的优势是代码绝对易于使用，只需 10 行代码就可以对文件进行排序。这些树被实现为模板，因此您可以将任何内容用作树项。项目只需要可比较。代码是自文档化的。类是 CAVLNode<class T>、CAVLTree<class T> 和 CAVLTreeIterator<class T>。

这是一个对文件进行排序的示例（文件不应包含相同的行，否则将消除重复项）

// sample code
#include <fstream.h>
#include "AVLBaum.h"

void SortFile(const char* ifname, const char* ofname)
{
	ifstream is(ifname);
	ofstream os(ofname);
	char buffer[255];
	CAVLTree<CString> tree;
	while (is.getline(buffer, sizeof(buffer)-1)
		tree.Insert(new CString(buffer));
	CAVLTreeIterator<CString> iter(tree);
	while (iter)
	{
		os << *(iter.GetData()) << endl;
		iter++;
	}
}

// end of sample code