Programming Help

Web Development



What's Here?

  • Members: 136,558
  • Replies: 479,684
  • Topics: 74,753
  • Snippets: 2,567
  • Tutorials: 677
  • Total Online: 1,921
  • Members: 77
  • Guests: 1,844

Welcome to Dream.In.Code
Getting C++ Help is Easy!

Join 136,558 C++ Programmers for FREE! Get instant access to thousands of C++ experts, tutorials, code snippets, and more! There are 1,921 people online right now. Registration is fast and FREE... Join Now!




AVL Tree Node Height Function

 
 Reply to this topicStart new topic

AVL Tree Node Height Function
wiIbur
6 May, 2008 - 09:27 AM
Post #1

New D.I.C Head
*

Joined: 25 Sep, 2007
Posts: 20


My Contributions
I have been searching around on the net as well as here to try and find some sort of AVL node height function that made an ounce of sense to me. Here is the one from the C++ AVL tutuorial found here:
http://www.dreamincode.net/forums/showtopic43916.htm
CODE
  /*
      Return the height of node t or -1 if NULL.
    */  
    int height( AvlNode *t ) const  
    {  
       return t == NULL ? -1 : t->height;  
    }  


I am working with a direct access file implementation of an AVL tree. I feel rather confident in my ability to fix this function to my needs, if I could make sense of it first. Would someone care to explain it? Namely what 'const' does, and the return. Thanks.
User is offlineProfile CardPM
+Quote Post

Cerolobo
RE: AVL Tree Node Height Function
6 May, 2008 - 09:33 AM
Post #2

D.I.C Regular
Group Icon

Joined: 5 Apr, 2008
Posts: 440



Thanked: 31 times
My Contributions
The const at the end of the int height( AvlNode *t ) means that no external data will be modified in the function (you can modify local variables though).

Here is the if statement expansion of the below code

Original
CODE

return t == NULL ? -1 : t->height;  


Expanded
CODE

if(t == NULL)
  return -1;
else
  return t->height;
User is offlineProfile CardPM
+Quote Post

wiIbur
RE: AVL Tree Node Height Function
6 May, 2008 - 09:38 AM
Post #3

New D.I.C Head
*

Joined: 25 Sep, 2007
Posts: 20


My Contributions
I don't exactly see how it is calculating the node height. If all it does it return the height, that's lame and not what I want.
User is offlineProfile CardPM
+Quote Post

Cerolobo
RE: AVL Tree Node Height Function
6 May, 2008 - 09:39 AM
Post #4

D.I.C Regular
Group Icon

Joined: 5 Apr, 2008
Posts: 440



Thanked: 31 times
My Contributions
I haven't actually read through the tutorial you posted, but yes, it's just returning the height, which is stored in a member variable.
User is offlineProfile CardPM
+Quote Post

skaoth
RE: AVL Tree Node Height Function
6 May, 2008 - 12:02 PM
Post #5

D.I.C Regular
Group Icon

Joined: 7 Nov, 2007
Posts: 343



Thanked: 10 times
Dream Kudos: 100
My Contributions
If all your looking to do is calculate the height of the tree and you simply
just need to traverse the left most subtree. As you know AVL trees are balanced
meaning that the 2 sub-trees do not vary by more than 1.

So to find the height. start from the root and go down the left side of the the
tree until you hit null.
User is online!Profile CardPM
+Quote Post

wiIbur
RE: AVL Tree Node Height Function
6 May, 2008 - 09:50 PM
Post #6

New D.I.C Head
*

Joined: 25 Sep, 2007
Posts: 20


My Contributions
QUOTE(skaoth @ 6 May, 2008 - 01:02 PM) *

If all your looking to do is calculate the height of the tree and you simply
just need to traverse the left most subtree. As you know AVL trees are balanced
meaning that the 2 sub-trees do not vary by more than 1.

So to find the height. start from the root and go down the left side of the the
tree until you hit null.


oh. thanks.
User is offlineProfile CardPM
+Quote Post

Reply to this topicStart new topic
Time is now: 12/2/08 11:30PM
Invision Power Board v2.1.7 © 2008  IPS, Inc.
Licensed to: MediaGroup1

Live C++ Help!

C++ Tutorials

Reference Sheets

C++ Snippets

DIC Chatroom

Bye Bye Ads

Monthly Drawing

Thumb Drive

Top Contributors

Top 10 Kudos This Month