Reply
Old 05-25-2014, 06:06 AM   #1 (permalink)
Ana
 
Status: Member
Posts: 50



Default count the height of leftsubtree and rightsubtree in an avl tree

So, I am trying to make AVL Tree in Java. Is it right if I try to create AVL by modifying my BST program? I started by making some new methods like singlerotation and doublerotation. But I don't know how to count the balance factor because first you have to know the left and right subtree height. Thus, it'll be balancefactor = height(left subtree) - height(right subtree);



How do I get height(left subtree) and height(right subtree)?
Ana is offline   Reply With Quote
Old 05-25-2014, 06:06 AM   #2 (permalink)
 
Status: Senior Member
Posts: 719



Default count the height of leftsubtree and rightsubtree in an avl tree

You can compute the height by recursively computing the heights of the two subtrees, taking the maximum of the two, and adding one (for the current node).

But recomputing this each time will be really slow; instead, the height of the node should be stored as part of the node's data and updated as necessary when rotations are made.

It is possible to store the height balance instead of the height (which can save some memory), but I find it easier to store the actual height.

Starting from a binary search tree is a good idea.
Money07 is offline   Reply With Quote
more..

Reply

Bookmarks

Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Designing website, width and height dimensions. I dont want it to scroll down what height? LukeE JavaScript 2 12-05-2013 11:06 AM
Height of Binary Tree? Jake Programming Languages 0 11-24-2013 11:05 PM
Binary Tree height Java programming? Jake Programming 0 11-17-2013 11:07 PM
How can i count the occurrences of words in a tree? (Java)? scout Programming 1 04-26-2012 03:37 PM
program in c that ask your height in integer centimeter and then convert your height to feet and inches? Unknown_User Programming 1 01-01-2012 12:36 PM