Декартово дерево

Да, с массивами теоретически можно делать (т.е. везде вместо указателей использовать индексы в массиве). Но вот без ссылок - заметно более громоздко получится.

Компактная реализация сильно использует хитрости массивов/указателей, поэтому без их понимания разобраться в реализации будет непросто.

• item - это структура данных, представляющая собой одну вершину дерева.

• pitem - это указатель на структуру item. Такие указатели мы используем, чтобы хранить связи между вершинами: т.е. левый и правый сын каждой вершины - это указатели, указывающие на некоторые другие вершины (или NULL, если не указывает никуда). Да и корень дерева root - тоже указатель, он указывает на вершину-корень. В общем, всё дерево написано на указателях

• Что вообще такое ссылка в C++. Упрощенное понимание такое: если у функции какой-то параметр является ссылкой, то внутри функции мы можем присваивать этому параметру какое-нибудь значение, и это значение запишется в передаваемую переменную.

• pitem & - это ссылка на указатель. Это самый сложный для понимания момент. Давайте посмотрим на одно из мест, где это используется: функция split(). Этой функции передаётся дерево t, ключ key, по которому надо разрезать дерево t, а результат этой функции кладётся в параметры l и r. Соответственно, для чего параметры l и r сделаны ссылками на pitem? Например, чтобы мы могли вызвать эту функцию с аргументом l равным t.r, аргументом r равным чему-нибудь ещё, и результат разрезания записался бы в t.r.

Всё равно, конечно, получилось сумбурно и запутанно, но надеюсь, что вы что-нибудь поймете из моего объяснения.