Как найти левых и правых детей корня в куче Леонардо?

Давайте представим, что у вас есть куча Леонардо порядка k, сохраненная в массиве, и вы рекурсивно выполняете компоновку так, чтобы вы всегда размещали большее поддерево, затем меньшее поддерево, а затем корневой узел. Это означает, что в массиве будет всего L (k) узлов в позициях с номерами 0, 1, 2, 3 …, L (k) — 1. Это будет выглядеть примерно так:

+---------------------------+----------------------+------+
|    Tree of order k - 1    | Tree of order k - 2  | root |
+---------------------------+----------------------+------+

Обратите внимание, что корень идет последним, поэтому он находится в позиции L (k) — 1, потому что мы используем нулевую индексацию.

Так где же два поддерева? Ну, поддерево порядка k — 2 находится непосредственно перед корневым узлом. Он выложен так, что его корень находится далеко справа. Таким образом, чтобы найти его корень, мы идем к корню всего дерева (позиция L (k) — 1) и возвращаемся на один шаг назад, чтобы добраться до позиции L (k) — 2.

Как насчет поддерева порядка k — 1? Ну, обратите внимание, что это удобно в передней части нашего представительства. Его корневой узел будет находиться в конце этого блока, который находится в позиции L (k — 1) — 1 (аналогично тому, как наше большее дерево порядка k имеет свой корень в позиции L (k) — 1.)

Надеюсь, вам понравилась моя статья! 🙂