Height of a red black tree

I'm almost done implementing a red black tree but I'm stuck with height. (Not black height). Can anyone give me a hint or the concept on how to implement height? I know the formula but its not much of a help.

I thought of traversing each node and adding a counter but this gets complicated as the red black tree gets bigger.

Basically how do I know when it has travelled down to its longest path?

Answers


There is a simple recursive approach for computing the height of a tree that works in time O(n), where n is the number of nodes. The idea is to compute the heights of each node's children, then to take the maximum of those values, plus one. Here's some pseudocode:

function treeHeight(node n) {
    if (n is null) return -1;
    return max(treeHeight(n.left), treeHeight(n.right)) + 1;
}

This visits every node exactly once and does O(1) work per node, so the total time complexity is O(n).

Hope this helps!


Need Your Help

Can an app be written to run on any devices?

app-store device hybrid-mobile-app mobile-devices

I would like to know if it is possible to write apps that can run on any devices.

Why move the key.snk file to the Properties folder in Sharepoint projects?

sharepoint-2010 strongname snk strong-named-key

It is "de rigeuer" here to move the key.snk file generated when a new project is created from its default location at the bottom of the Solution up into the Properties folder.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.