Любой может объяснить computeRedLevel (int sz) в Java TreeMap?

Question

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

Я не могу понять, как этот алгоритм работает для вычисления уровня красного? Может ли кто-нибудь объяснить это?

Answer 1

В соответствии с реализацией метод computeRedLevel(int size) вызывается методом buildTree(), который присваивает всем узлам BLACK. Это последний полный уровень полного бинарного дерева, созданного методом buildTree().

Теперь, как TreeMap использует Red Black Tree и RBT является self balancing binary search tree, идти до последнего уровня с вершины будет уменьшить размер на 2 при каждой итерации, как высота себя балансирование BST является O(logn).

Следовательно, это вернет последний уровень.

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

Answer 2

Описание computeRedLevel

Найти уровень вниз, к которому присвоить все узлы ЧЕРНЫЙ. Это последний «полный» уровень полного бинарного дерева, созданного buildTree.

Во-первых, трассировка назад sz, установлено, что sz - размер скопированной карты. Во-вторых, TreeMap поддерживается Red-Black Tree (RBT), на котором черные высоты одинаковы.

относительно всех элементов в скопированной карте как узлы в полном двоичном дереве и окрашивания всех узлов в идеальной части complete binary tree черным, легко удовлетворят функцию RBT.

computeRedLevel(int sz) Используется для вычисления уровня идеальной бинарной части дерева полного бинарного дерева. Например, уровень совершенной части полного бинарного дерева в рисунке: 3. так compteRedLevel(11) равно 3. an complete tree