任何人都可以在Java TreeMap中解释computeRedLevel（int sz）？

private static int computeRedLevel(int sz) { 
    int level = 0; 
    for (int m = sz - 1; m >= 0; m = m/2 - 1) 
     level++; 
    return level; 
}

我不明白这个算法是如何计算红色水平的？有人可以解释吗？任何人都可以在Java TreeMap中解释computeRedLevel（int sz）？

你所说的“为什么它可以计算红色级别”的意思是？ –

@SleimanJneidi我的意思是这个算法是如何工作的。 – user2916610

@ user2916610您是否阅读了解释'TreeMap'源代码中的方法的注释？摘录：_这个级别的数字是通过查找到达零度节点所需的分割数来计算的。 –

按照实施方式，方法computeRedLevel(int size)由buildTree()方法调用，该方法将所有节点分配为BLACK。这是由buildTree()方法生成的完整二叉树的最后一个完整级别。

现在，TreeMap使用Red Black Tree和彩铃是一个self balancing binary search tree，去从顶部的最后一级，将通过2在每次迭代的自我平衡BST的高度减小尺寸O(logn)。

因此，这将返回最后一级。

说明

for (int m = sz - 1; m >= 0; m = m/2 - 1) 
     level++; 
    return level;

2016-03-09 13:08:53 FallAndLearn

computeRedLevel

查找到其指定的所有节点黑电平。这是buildTree生成的完整二叉树的最后一个“完整”级别。

首先，追溯回sz，发现sz是复制地图的大小。二，TreeMap支持红黑树（RBT），其上的黑色高地是相同的。

将复制地图中的所有元素作为一个完整的二叉树中的节点，并着色为黑色完美部分中的所有节点，将很容易满足RBT的特征。

computeRedLevel(int sz)用于计算完整二叉树的完美二叉树部分的级别。例如，完全二叉树的在下面的图片完美的部分的级别为3所以compteRedLevel(11)是3 an complete tree

2016-08-07 13:57:24

回答