📄 avl.shtml
字号:
<HTML><!-- Header information--><HEAD> <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1"> <META NAME="Author" CONTENT="Guy Gascoigne - Piggford"> <TITLE>C++ - AVLTree - template version </TITLE></HEAD><!-- Set background properties --><body background="../fancyhome/back.gif" bgcolor="#FFFFFF" link="#B50029" vlink="#8E2323" alink="#FF0000" bgproperties="fixed"><!-- A word from our sponsors... --><table WIDTH="100%"><tr WIDTH="100%"><td align=center><!--#exec cgi="/cgi/ads.cgi"--><td></tr></table><!-- Article Title --><CENTER><H3><FONT COLOR="#AOAO99">AVLTree - template version</FONT></H3></CENTER><CENTER><H3><HR></H3></CENTER><!-- Author and contact details -->This article was contributed by <A HREF="mailto:Jaeger-Geitersdorf@t-online.de">Andreas J鋑er</A>.<!-- The article... --><p>I have implemented the binary tree's of Addison-Velski and Landis(AVL-Tree's), which allow Standard-operation like Insert, Search and deletein logarithmical time. Ordinary binary trees can become very obscure, theycan become a linear structure and the basic operations take linear and notlogarithmical time. The advantage of the AVL-Tree's is a strategy ofrestructurate the tree after Insert- and Delete-operations. Therestructuration itself only takes logarithmical time. So the trees arehigh-efficient binary trees to hold a large number of items. I use suchtrees to sort data. The sort of data using AVL-Trees takes n*log(n)-time,so you can sort a lot of data in optimal time. I have sorted with thattechnology hundrets of thousands of items, within a quarter of an hour. Itis very easy to eliminate duplicates, duplicates will not be inserted inthe tree. What other algorithm works so efficient??? And the greatestadvantage is, that the code is absolutely easy to use, 10 lines are enoughto sort a file. The Trees are implemented as templates, so you can useeverything you want as item. Items only must be comparable. The code isself-documentating. The classes are CAVLNode<class T>, CAVLTree<class T>and CAVLTreeIterator<class T>.<p>Here is an example to sort a file:<pre><tt><font COLOR="#990000">// sample code#include "AVLBaum.h"void SortFile(const char* iname, 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</font></tt></pre>And now the "AVLBaum.h":<pre><tt><font COLOR="#990000">// Creator: Andreas J鋑er// Ortsstr. Nr. 2// D-07407 Geitersdorf//// Last updated: 04. April 1998// e-mail: Jaeger-Geitersdorf@t-online.de//// you can use and modify that code free when preserving// the name of the creator//// have fun!//////////////////////////////////////////////////////////////////// Note: //// there must be a function T::Compare(T&) //// or the function Compare of teh Template-Klasse //// CAVLNode<T> has to be overridden. //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Vorbemerkungen: //// Es mu⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -