AVL Tree code
Avi Pilosof
I'm trying to write code for them, but I ain't getting balanced trees :)
The fact that the trees don't even come out properly ordered worries mee
too...
C/C++ cource would be great, but pseudocode will do nicely too.
TIA
###################################################################
Avi Pilosof - av...@cse.unsw.edu.au
- http://www.cse.unsw.edu.au/~avip/
> Marketing is simply sales with a college education.
Menno Victor van der Star
>Does anyone have experience with AVL trees?
>
>I'm trying to write code for them, but I ain't getting balanced trees :)
>
>The fact that the trees don't even come out properly ordered worries mee
>too...
>
>C/C++ cource would be great, but pseudocode will do nicely too.
>
Here's an implementation in pascal, I hope this is good enough for you!
Ciao,
Menno
--- Code follows ---
Unit AVL;
Interface
Type
KeyType = LongInt;
AVLNodePtr = ^AVLNode;
AVLNode = Object
balFac : Integer;
value : KeyType;
Left, Right : AVLNodePtr;
Constructor Init (val : KeyType);
Function add (val : KeyType) : AVLNodePtr;
Function remove (val : KeyType; Var junk : AVLNodePtr) : AVLNodePtr;
Function SingleRotateLeft : AVLNodePtr;
Function SingleRotateRight : AVLNodePtr;
Function RestoreLeftBalance (oldbf : Integer) : AVLNodePtr;
Function RestoreRightBalance (oldbf : Integer) : AVLNodePtr;
Function Balance : AVLNodePtr;
Function RemoveLeftMostDescendant (Var childptr : AVLNodePtr) : AVLNodePtr;
End;
AVLTreePtr = ^AVLTree;
AVLTree = Object
Constructor Init;
Destructor Done;
Procedure Add (val : KeyType);
Procedure Remove (val : KeyType);
Function Get (val : KeyType) : AVLNodePtr;
Private
Root : AVLNodePtr;
End;
Implementation
Constructor AVLNode.Init (val : KeyType);
Begin
Value:=val;
Left:=NIL;
Right:=NIL;
balFac:=0;
End;
Function AVLNode.Add (val : KeyType) : AVLNodePtr;
Var
oldbf : Integer;
Begin
If (val<value) then Begin
If left<>NIL then Begin
oldbf:=left^.balFac;
Left:=left^.add (val);
If (left^.balFac<>oldbf) And (left^.balFac<>0) then Dec (balFac);
End Else Begin
Left:=New (AVLNodePtr,Init (val));
Dec (balFac);
End;
End Else Begin
If right<>NIL then Begin
oldbf:=right^.balFac;
Right:=right^.add (val);
If (right^.balFac<>oldbf) And (right^.balFac<>0) then Inc (balFac);
End Else Begin
Right:=New (AVLNodePtr,Init (val));
Inc (balFac);
End;
End;
If (balFac<-1) Or (balFac>1) then
add:=Balance
Else
add:=@SELF;
End;
Function AVLNode.remove (val : KeyType; Var junk : AVLNodePtr) : AVLNodePtr;
Var
newroot : AVLNodePtr;
oldbf : Integer;
Begin
If (val=value) then Begin
junk:=@SELF;
If right=NIL then Begin remove:=left; Exit; End;
oldbf:=right^.balFac;
Right:=right^.RemoveLeftMostDescendant (newroot);
newroot^.Left:=Left;
newroot^.Right:=Right;
newroot^.balFac:=balFac;
remove:=newroot^.restoreRightBalance (oldbf);
Exit;
End Else If (val<value) then Begin
If left=NIL then Begin remove:=@SELF; Exit; End;
oldbf:=left^.balFac;
Left:=left^.remove (val,junk);
remove:=restoreLeftBalance (oldbf);
Exit;
End Else Begin
If right=NIL then Begin remove:=@SELF; Exit; End;
oldbf:=right^.balFac;
Right:=right^.remove (val,junk);
remove:=restoreRightBalance (oldbf);
Exit;
End;
End;
Function AVLNode.SingleRotateLeft : AVLNodePtr;
Var
nodeA, nodeB : AVLNodePtr;
Abf, Bbf : Integer;
Begin
nodeA:=@SELF;
nodeB:=nodeA^.right;
nodeA^.Right:=nodeB^.left;
nodeB^.Left:=nodeA;
Abf:=nodeA^.balFac;
Bbf:=nodeB^.balFac;
If (Bbf<=0) then Begin
If (Abf>=1) then
nodeB^.balFac:=Bbf-1
Else
nodeB^.balFac:=Abf+Bbf-2;
nodeA^.balFac:=Abf-1;
End Else Begin
If (Abf<=Bbf) then
nodeB^.balFac:=Abf-2
Else
nodeB^.balFac:=Bbf-1;
nodeA^.balFac:=(Abf-Bbf)-1;
End;
SingleRotateLeft:=nodeB;
End;
Function AVLNode.SingleRotateRight : AVLNodePtr;
Var
nodeA, nodeB : AVLNodePtr;
Abf, Bbf : Integer;
Begin
nodeA:=@SELF;
nodeB:=nodeA^.left;
nodeA^.Left:=nodeB^.right;
nodeB^.Right:=nodeA;
Abf:=nodeA^.balFac;
Bbf:=nodeB^.balFac;
If (Bbf<=0) then Begin
If (Bbf>Abf) then
nodeB^.balFac:=Bbf+1
Else
nodeB^.balFac:=Abf+2;
nodeA^.balFac:=1+Abf-Bbf;
End Else Begin
If (Abf<=-1) then
nodeB^.balFac:=Bbf+1
Else
nodeB^.balFac:=Abf+Bbf+2;
nodeA^.balFac:=1+Abf;
End;
SingleRotateRight:=nodeB;
End;
Function AVLNode.RestoreLeftBalance (oldbf : Integer) : AVLNodePtr;
Var
leftchild : AVLNodePtr;
Begin
leftchild:=left;
If Not Assigned (leftchild) then
Inc (balFac)
Else
If (leftchild^.balFac<>oldbf) And (leftchild^.balFac=0) then Inc (balFac);
If (balFac>1) then
RestoreLeftBalance:=Balance
Else
RestoreLeftBalance:=@SELF;
End;
Function AVLNode.RestoreRightBalance (oldbf : Integer) : AVLNodePtr;
Var
rightchild : AVLNodePtr;
Begin
rightchild:=right;
If Not Assigned (rightchild) then
Dec (balFac)
Else
If (rightchild^.balFac<>oldbf) And (rightchild^.balFac=0) then Dec (balFac);
If (balFac<-1) then
RestoreRightBalance:=Balance
Else
RestoreRightBalance:=@SELF;
End;
Function AVLNode.Balance : AVLNodePtr;
Begin
If (balFac<0) then Begin
If (left^.balFac<=0) then Begin
Balance:=SingleRotateRight;
Exit;
End Else Begin
Left:=left^.SingleRotateLeft;
Balance:=SingleRotateRight;
Exit;
End;
End Else Begin
If (right^.balFac>=0) then Begin
Balance:=SingleRotateLeft;
Exit;
End Else Begin
Right:=right^.SingleRotateRight;
Balance:=SingleRotateLeft;
Exit;
End;
End;
End;
Function AVLNode.RemoveLeftMostDescendant (Var childptr : AVLNodePtr) : AVLNodePtr;
Var
leftchild : AVLNodePtr;
oldbf : Integer;
Begin
leftchild:=left;
If Not Assigned (leftchild) then Begin
childptr:=@SELF;
RemoveLeftMostDescendant:=right;
Exit;
End;
oldbf:=leftchild^.balFac;
Left:=leftchild^.RemoveLeftMostDescendant (childptr);
RemoveLeftMostDescendant:=RestoreLeftBalance (oldbf);
End;
Constructor AVLTree.Init;
Begin
Root:=NIL;
End;
Destructor AVLTree.Done;
Begin
End;
Procedure AVLTree.Add (val : KeyType);
Begin
If Assigned (root) then
root:=root^.add (val)
Else
root:=New (AVLNodePtr,Init (val));
End;
Procedure AVLTree.Remove (val : KeyType);
Var
eliminateNode : AVLNodePtr;
Begin
eliminateNode:=NIL;
If Assigned (root) then
root:=root^.remove (val,eliminateNode);
If Assigned (eliminateNode) then Dispose (eliminateNode);
End;
Function AVLTree.Get (val : KeyType) : AVLNodePtr;
Var
Walker : AVLNodePtr;
Begin
Walker:=Root;
While Assigned (Walker) And (Walker^.Value<>val) Do Begin
If Walker^.Value<val then Walker:=Walker^.Right Else Walker:=Walker^.Left;
End;
Get:=Walker;
End;
End.
Paul Wilson
Avi Pilosof <av...@cse.unsw.edu.au> wrote:
>Does anyone have experience with AVL trees?
>
>I'm trying to write code for them, but I ain't getting balanced trees :)
>
>The fact that the trees don't even come out properly ordered worries mee
>too...
>
>C/C++ cource would be great, but pseudocode will do nicely too.
I believe that AVL trees come as part of the GNU language stuff distribution,
in libg++ and other related directories.
As I recall, there are AVL trees in genclass form (an ugly preprocessor
system that fakes templates---the code was written before templates
actually worked). There may be AVL trees in the STL (Standard Template
Library). (GNU STL, based on the free HP STL, is included somewhere
in the GNU distribution.)
You should also consider red-black trees, which are widely regarded
as a simpler and faster replacement for AVL trees. I believe that
there are red-black trees in STL.
More interestingly, check out splay trees. Splay trees are agressively
adaptive and can be *way* faster than AVL or red-black trees if there's
locality in your input data. Their worst-case is worse, but their
amortized complexity is withing a constant of AVL or red-black trees'.
(That means that for a long enough sequence of inputs, the bad cases
will be balanced by good cases.)
Splay trees deserve serious consideration for large trees that have
to be very fast.
--
| Paul R. Wilson, Comp. Sci. Dept., U of Texas @ Austin (wil...@cs.utexas.edu)
| Papers on memory allocators, garbage collection, memory hierarchies,
| persistence and Scheme interpreters and compilers available via ftp from
| ftp.cs.utexas.edu, in pub/garbage (or http://www.cs.utexas.edu/users/wilson/)
Avi Pilosof
: You should also consider red-black trees, which are widely regarded
: as a simpler and faster replacement for AVL trees. I believe that
: there are red-black trees in STL.
I've never heard of these. Could you explain (in a sentence or two) what
the theory for these is?
: More interestingly, check out splay trees. Splay trees are agressively
: adaptive and can be *way* faster than AVL or red-black trees if there's
: locality in your input data. Their worst-case is worse, but their
: amortized complexity is withing a constant of AVL or red-black trees'.
: (That means that for a long enough sequence of inputs, the bad cases
: will be balanced by good cases.)
Hmmm...I read about splay trees somewhere, but never paid them too much
attention. I think I know where...I'll look it up again. Thanks.
Avi Pilosof
: splay trees are truly cool technology - definitely read up on them. Splay
: trees can be also used as a dynamic huffman tree structure buf thats a
: different story....
I've done some web searching, and all I could find was splay trees with
ref to compression & encryption.
However, several people did post/mail me stuff regarding red/black &
splay trees, and I'd like to thank them all.
Now I've just got to find time to look these things up and implement them.
###################################################################
Avi Pilosof - av...@cse.unsw.edu.au
- http://www.cse.unsw.edu.au/~avip/
> Why can't women remember to put the seat back up?
Damien Morton
Pilosof) wrote:
> Paul Wilson (wil...@cs.utexas.edu) wrote:
>
> : You should also consider red-black trees, which are widely regarded
> : as a simpler and faster replacement for AVL trees. I believe that
> : there are red-black trees in STL.
>
> I've never heard of these. Could you explain (in a sentence or two) what
> the theory for these is?
>
> : More interestingly, check out splay trees. Splay trees are agressively
> : adaptive and can be *way* faster than AVL or red-black trees if there's
> : locality in your input data. Their worst-case is worse, but their
> : amortized complexity is withing a constant of AVL or red-black trees'.
> : (That means that for a long enough sequence of inputs, the bad cases
> : will be balanced by good cases.)
>
> Hmmm...I read about splay trees somewhere, but never paid them too much
> attention. I think I know where...I'll look it up again. Thanks.
>
> ###################################################################
>
> Avi Pilosof - av...@cse.unsw.edu.au
> - http://www.cse.unsw.edu.au/~avip/
>
> > Marketing is simply sales with a college education.
splay trees are truly cool technology - definitely read up on them. Splay
trees can be also used as a dynamic huffman tree structure buf thats a
different story....
Damien Morton
Paul Snively
> Paul Wilson (wil...@cs.utexas.edu) wrote:
>
> : You should also consider red-black trees, which are widely regarded
> : as a simpler and faster replacement for AVL trees. I believe that
> : there are red-black trees in STL.
>
> I've never heard of these. Could you explain (in a sentence or two) what
> the theory for these is?
>
> : More interestingly, check out splay trees. Splay trees are agressively
> : adaptive and can be *way* faster than AVL or red-black trees if there's
> : locality in your input data. Their worst-case is worse, but their
> : amortized complexity is withing a constant of AVL or red-black trees'.
> : (That means that for a long enough sequence of inputs, the bad cases
> : will be balanced by good cases.)
>
> Hmmm...I read about splay trees somewhere, but never paid them too much
> attention. I think I know where...I'll look it up again. Thanks.
And while you're at that, check out SkipLists, a probabilistic data
structure that delivers expected O(log N) time for insertion, deletion, or
search, with the probability of a worst-case scenario being
parameterizable so as to be arbitrarily small. See
ftp://ftp.cs.umd.edu/pub/skipLists
for papers and code in Pascal or C.
Hope this helps,
>##########################################################>#########
>
> Avi Pilosof - av...@cse.unsw.edu.au
> - http://www.cse.unsw.edu.au/~avip/
>
> > Marketing is simply sales with a college education.
Paul Snively
ch...@chelsea.ios.com
--
To get random signatures put text files into a folder called ³Random Signatures² into your Preferences folder.
Paul Wilson
Avi Pilosof <av...@cse.unsw.edu.au> wrote:
>Damien Morton (dm...@ozemail.com.au) wrote:
>
>: splay trees are truly cool technology - definitely read up on them. Splay
>: trees can be also used as a dynamic huffman tree structure buf thats a
>: different story....
>
>ref to compression & encryption.
>
>However, several people did post/mail me stuff regarding red/black &
>splay trees, and I'd like to thank them all.
>
>Now I've just got to find time to look these things up and implement them.
Here's the essential reference for splay trees, from the _Journal_of_
the_ACM_ article that introduced them.
@article{ST:SABST,
author = "Daniel Dominic Sleator and Robert Endre Tarjan",
title = "Self-Adjusting Binary Search Trees",
journal = jacm,
volume = 32, number = 3, year = 1985
}
I forgot to mention another advantage: they're much easier to understand
and implement than AVL trees.
Klamer Schutte
:Paul Wilson (wil...@cs.utexas.edu) wrote:
:: You should also consider red-black trees, which are widely regarded
:: as a simpler and faster replacement for AVL trees. I believe that
:: there are red-black trees in STL.
In the current implementation - yes. But more binary trees will do if
you follow the specification for STL.
:I've never heard of these. Could you explain (in a sentence or two) what
:the theory for these is?
red-black trees are balanced binary trees. But you probably already knew
that :-)
A nice treatment of Red-black tree code can be found in
"Introduction to Algorithms", by Cormen et al (MIT Press, 1990).
--
Klamer Schutte -- +31-15-2786054 -- kla...@ph.tn.tudelft.nl
http://www.ph.tn.tudelft.nl/People/klamer/Klamer.html
Ken Clarkson
ftp://spade.pc.cs.cmu.edu/usr/sleator/public/top-down-splay.c.
-Ken