二叉搜索树<高度

本文关键字：高度 搜索树 | 更新日期: 2023-09-27 17:54:35

我即将实现一个很好的二叉搜索树。有人知道如何计算二进制搜索树TKey, TValue高度吗?谢谢!现在我用这个来求任意BST树的高度。但在这种情况下，它似乎不起作用。

     public int Height()
    {
        return height(root);
    }
    protected int height(Node tree)
    {
        if (tree == null)
            return -1;
        int lefth = height(tree.left);
        int righth = height(tree.right);
        if (lefth > righth)
            return lefth + 1;
        else
            return righth + 1;

    }

二叉搜索树<高度

你知道你已经有一个了吗?

System.Collections.Generic.SortedSet<T>为红黑树(高度平衡)。

如果这还不够，你也有C5集合库，它给你其他的红黑树实现:

  • TreeSet<T>

    表示使用平衡红黑树的一组项目;参见13.10节。按索引或按项值访问项需要时间O(log n)和项插入时间项删除时间O(log n)平摊。树集不允许因此属性AllowsDuplicates为false。

  • TreeBag<T>

    表示使用平衡红黑树的物品的包或多集。按索引或按项值访问项需要时间O(log n)和项插入时间和项删除时间O(log n)平摊。

    tree bag允许复制，所以属性AllowsDuplicates为true，并且每个项等价类只存储一个代表，因此DuplicatesByCounting为真

  • TreeDictionary<K,V>

    表示一个由(键、值)对或项组成的字典平衡红黑二叉树。条目访问、条目删除和条目插入取时间O(log n)。树的键、值或项的枚举字典遵循键比较器确定的键顺序。

进城去吧，但除非你真的想，为什么要重新发明轮子呢?

private static int getHeight(BTreeNode n){

if(n == null)
    return 0;
int lHeight = getHeight(n.left);
int rheight = getHeight(n.right);
int height = 1+Math.max(lHeight,rheight);
return height;

}

相关文章：