使用递归的红黑树高度 [英] Red-Black Tree Height using Recursion

问题描述

我有以下这些方法来获得一个红黑树的高度，这工作（我发送根）。现在我的问题是，这是如何工作？我画了一棵树，并尝试按照这一步一步一步的每个递归调用，但我不能拉掉。
我知道代码在做什么的一般想法，这是通过所有的叶子和比较它们，但任何人都可以清楚地解释这一点？

I have these following methods to get the height of a red black tree and this works (I send the root). Now my question is, how is this working? I have drawn a tree and have tried following this step by step for each recursion call but I can't pull it off. I know the general idea of what the code is doing, which is going through all the leaves and comparing them but can anyone give a clear explanation on this?

int RedBlackTree::heightHelper(Node * n) const{
        if ( n == NULL ){
            return -1;
        }
        else{
            return max(heightHelper(n->left), heightHelper(n->right)) + 1;
        }
    }

int RedBlackTree::max(int x, int y) const{
    if (x >= y){
        return x;
    }
    else{
        return y;
    }
}

推荐答案

，通用算法找到任何二叉树的高度（BST，AVL树，红黑等）如下

Well, the general algorithm to find the height of any binary tree (whether a BST,AVL tree, Red Black,etc) is as follows

For the current node:
 if(node is NULL) return -1
 else
    h1=Height of your left child//A Recursive call
    h2=Height of your right child//A Recursive call
    Add 1 to max(h1,h2) to account for the current node
    return this value to parent.

上述算法的说明如下：

（图片提供< a href =http://en.wikipedia.org/wiki/Binary_search_tree =nofollow> Wikipedia.org ）

这篇关于使用递归的红黑树高度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！