Click here to Skip to main content
Click here to Skip to main content

AVL Binary Tree for C++

, 4 Jan 2006
Rate this:
Please Sign up or sign in to vote.
Using the HeightBalancedTree C++ template as an array or as a sorted sequence.

Introduction

Very often, I had 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

About the Author

Dimiter Georgiev

Bulgaria Bulgaria
No Biography provided

Comments and Discussions

 
GeneralYou have my 5 PinmemberPablo Yabo14-Oct-10 4:41 
GeneralCouple of observations... Pinmemberyafan5-Jan-06 4:30 
GeneralRe: Couple of observations... PinmemberDimiter Georgiev5-Jan-06 5:42 
GeneralAnother Wish List Item Pinmemberscott035629-Dec-05 1:38 
GeneralAnother Wish List Item Pinmemberscott035620-Dec-05 8:46 
GeneralRe: Another Wish List Item PinmemberDimiter Georgiev21-Dec-05 1:35 
GeneralRe: Another Wish List Item PinmemberDimiter Georgiev21-Dec-05 1:36 
GeneralRe: Another Wish List Item PinmemberDimiter Georgiev21-Dec-05 11:41 
GeneralLatest Version PinmemberDimiter Georgiev15-Dec-05 4:25 
GeneralWish List... PinmemberJimD.999914-Dec-05 6:14 
GeneralRe: Wish List... PinmemberDimiter Georgiev14-Dec-05 6:20 
GeneralRe: Wish List... PinmemberDimiter Georgiev14-Dec-05 6:49 
GeneralRe: Wish List... PinmemberDimiter Georgiev14-Dec-05 6:54 
GeneralRe: Wish List... PinmemberJimD.999914-Dec-05 7:04 
GeneralRe: Wish List... PinmemberDimiter Georgiev14-Dec-05 7:29 
GeneralRe: Wish List... PinmemberDimiter Georgiev18-Dec-05 11:35 
GeneralLazy Delete Method PinmemberMichael Holm14-Dec-05 1:59 
GeneralRe: Lazy Delete Method PinmemberDimiter Georgiev14-Dec-05 3:01 
Questionwhat about STL's map/set ? PinmemberIftahh13-Dec-05 13:41 
AnswerRe: what about STL's map/set ? Pinmemberemilio_grv13-Dec-05 21:19 
GeneralRe: what about STL's map/set ? PinmemberGast12814-Dec-05 5:33 
GeneralRe: what about STL's map/set ? PinmemberJimD.999914-Dec-05 6:09 
GeneralRe: what about STL's map/set ? PinmemberGast12814-Dec-05 6:29 
GeneralRe: what about STL's map/set ? PinmemberJimD.999914-Dec-05 6:49 
GeneralRe: what about STL's map/set ? PinmemberGast12814-Dec-05 7:11 
GeneralRe: what about STL's map/set ? PinmemberJimD.999914-Dec-05 7:25 
AnswerRe: what about STL's map/set ? PinmemberDimiter Georgiev14-Dec-05 1:08 
AnswerRe: what about STL's map/set ? PinmemberMichael Holm14-Dec-05 2:00 
GeneralRe: what about STL's map/set ? PinmemberJörgen Sigvardsson5-Jan-06 8:45 

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

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

| Advertise | Privacy | Mobile
Web03 | 2.8.140721.1 | Last Updated 4 Jan 2006
Article Copyright 2005 by Dimiter Georgiev
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid