Click here to Skip to main content
15,867,835 members
Articles / Programming Languages / Objective C

AVL Binary Tree for C++

Rate me:
Please Sign up or sign in to vote.
4.64/5 (10 votes)
4 Jan 2006CPOL2 min read 160.1K   2.4K   38   30
Using the HeightBalancedTree C++ template as an array or as a sorted sequence

Introduction

Very often, I wanted a container that provides fast insertion and fast indexing. I also often had the need for sorted containers. Here, I present an AVL binary tree implementation that serves all these needs.

Background

Using the Code

You can use the HeightBalancedTree<> template as either a sequence container that supports fast arbitrary insertions and deletions of objects, or as a sorted container.

If you use the tree as a fast sequence container, use the methods InsertByIndex, FindByIndex, and RemoveByIndex.

If you use the tree as a sorted container, use the methods InsertComparable, FindComparable, and RemoveComparable. These methods use the user-provided Comparator type to compare the objects stored inside the container.

You can always use the overloaded operator[] that works just like FindByIndex. It throws a std::out_of_range exception if the index is invalid.

All by-index modification and access methods of the container take approximately O(log(n)) time.

All by-comparison modification and access methods of the container take approximately O(k * log(n)) time, where k is the time taken to compare any two objects.

Here's some sample code that creates and modifies a random-access array of size_ts:

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);
}

Here's some sample code that creates and modifies a sorted sequence of strings:

#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;
}

Points of Interest

Tell me what you think of this. I'm open to suggestions.

History

  • 2005, December, 14 - 1.0.1 Fixed a bug in FindComparable: the returned index was wrong
  • 2005, December, 13 - Initial version uploaded to CodeProject

License

This article has no explicit license attached to it, but may contain usage terms in the article text or the download files themselves. If in doubt, please contact the author via the discussion board below.

A list of licenses authors might use can be found here.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Bulgaria Bulgaria
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionThe Managed Environment Pin
Ben McNamara13-Sep-15 18:42
Ben McNamara13-Sep-15 18:42 
GeneralYou have my 5 Pin
Pablo Yabo14-Oct-10 4:41
professionalPablo Yabo14-Oct-10 4:41 
GeneralCouple of observations... Pin
yafan5-Jan-06 4:30
yafan5-Jan-06 4:30 
GeneralRe: Couple of observations... Pin
Dimiter Georgiev5-Jan-06 5:42
Dimiter Georgiev5-Jan-06 5:42 
GeneralAnother Wish List Item Pin
scott035629-Dec-05 1:38
scott035629-Dec-05 1:38 
GeneralAnother Wish List Item Pin
scott035620-Dec-05 8:46
scott035620-Dec-05 8:46 
GeneralRe: Another Wish List Item Pin
Dimiter Georgiev21-Dec-05 1:35
Dimiter Georgiev21-Dec-05 1:35 
GeneralRe: Another Wish List Item Pin
Dimiter Georgiev21-Dec-05 1:36
Dimiter Georgiev21-Dec-05 1:36 
GeneralRe: Another Wish List Item Pin
Dimiter Georgiev21-Dec-05 11:41
Dimiter Georgiev21-Dec-05 11:41 
GeneralLatest Version Pin
Dimiter Georgiev15-Dec-05 4:25
Dimiter Georgiev15-Dec-05 4:25 
GeneralWish List... Pin
JimD.999914-Dec-05 6:14
JimD.999914-Dec-05 6:14 
GeneralRe: Wish List... Pin
Dimiter Georgiev14-Dec-05 6:20
Dimiter Georgiev14-Dec-05 6:20 
GeneralRe: Wish List... Pin
Dimiter Georgiev14-Dec-05 6:49
Dimiter Georgiev14-Dec-05 6:49 
GeneralRe: Wish List... Pin
Dimiter Georgiev14-Dec-05 6:54
Dimiter Georgiev14-Dec-05 6:54 
GeneralRe: Wish List... Pin
JimD.999914-Dec-05 7:04
JimD.999914-Dec-05 7:04 
GeneralRe: Wish List... Pin
Dimiter Georgiev14-Dec-05 7:29
Dimiter Georgiev14-Dec-05 7:29 
GeneralRe: Wish List... Pin
Dimiter Georgiev18-Dec-05 11:35
Dimiter Georgiev18-Dec-05 11:35 
GeneralLazy Delete Method Pin
Just someone else14-Dec-05 1:59
Just someone else14-Dec-05 1:59 
GeneralRe: Lazy Delete Method Pin
Dimiter Georgiev14-Dec-05 3:01
Dimiter Georgiev14-Dec-05 3:01 
Questionwhat about STL's map/set ? Pin
Iftahh13-Dec-05 13:41
Iftahh13-Dec-05 13:41 
AnswerRe: what about STL's map/set ? Pin
Emilio Garavaglia13-Dec-05 21:19
Emilio Garavaglia13-Dec-05 21:19 
We must consider the difference between the facts and the myths:
STL is a specification with a number of different implementations.

The only thing STL specifications says about set/map is that they must be sorted and associative.
If I write myself a class having the same std::map interface and that store data in a reallocated array at each insertion, I’m still providing and STL compliant map class. Of course, about efficiency, we’ll have lot to discuss.

Moral: you can say STL is standard, not that it is robust.
You can say that a particular STL implementation is robust (or better: more robust than another).

About the PJ Plauger STL implementation provided by Microsoft with its compliers, yes … it uses black/red trees. Like every sorted contained based on binary trees, it has the same external behaviour as AVL, but the different algorithm used to keep them balanced make them differently performant in different situation.

B/R performs better in case of frequent insertion/deletions, AVL in case of frequent visit.
About robustness: if everyone use only existing code because is “robust” no new code can be provided and no emprovement in the IT science can exist.
Test it, correct it, and it’ll become robust as well everything else.
If you don’t have the time to do this … don’t use it, but don’t ask why invent it …

In a metaphor: if anyone marries only experienced girl to have children, no children can be done in after one generation.
Out of metaphor, if you have the presumption to write “for ever software” you're right.
If you think your software can –sooner or later- die, why never test something different in new software development?



2 bugs found.
> recompile ...
65534 bugs found.
D'Oh! | :doh:

GeneralRe: what about STL's map/set ? Pin
Gast12814-Dec-05 5:33
Gast12814-Dec-05 5:33 
GeneralRe: what about STL's map/set ? Pin
JimD.999914-Dec-05 6:09
JimD.999914-Dec-05 6:09 
GeneralRe: what about STL's map/set ? Pin
Gast12814-Dec-05 6:29
Gast12814-Dec-05 6:29 
GeneralRe: what about STL's map/set ? Pin
JimD.999914-Dec-05 6:49
JimD.999914-Dec-05 6:49 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.