сколько бит на узел

Question

Этот вопрос возник из упражнения Алгоритма 4. Я вставляю его здесь следующим образом: 3.3.19 Имея 1 бит на узел для цвета, мы можем представить 2-, 3- и 4-узлы. Сколько битов на узел нам нужно представить для 5-, 6-, 7- и 8-узлов с бинарным деревом?

Для цвета каждого узла есть только два цвета: черный и красный, либо красный или черный, затем самоочевидность, 1 бит информации на узел достаточно для того, что мы хотели бы представить. Почему он спрашивает, сколько бит на узел?

Answer 1

Поскольку 1 бит является достаточным для деревьев RB, которые являются просто другим представлением 2-3-4 деревьев, вопрос заключается в том, сколько бит необходимо для другой основы дерева.

8-узел будет иметь три внутренних уровня (запомните, сколько исходящих ссылок имеет узел, а не количество внутренних узлов):

    4
 2   6
1 3 5 7

Это завершит полный 8-узел. Можно было бы представить это как сине-красно-черное дерево (которое будет принимать два бита на узел, без использования одной комбинации битов).

colors = log_2 биты на основе дерева = ciel log_2 colors

Таким образом, с базисом дерева в 4 вам нужно 2 цвета и один бит, для базиса 8 вам нужно 3 цвета и 2 бита, для основы 16 потребуется 4 цвета, но все равно нужно всего 2 бита, 3 бита будут способен обрабатывать до 256 (8 цветов).