Какой тип бинарного дерева используется для Buddy аллокатора?

Question

[Имя]

Нужно реализовать Buddy аллокатор памяти, но не могу понять, какой тип бинарного дерева там используется, вроде как AVL, так ли это? И можно-ли где-то взять хорошую реализацию этого дерева на Си, дабы не писать велосипед?

Answer 1

[Wataru]

Нет, там не AVL дерево. Там просто полное дерево из всех блоков. Фиксированное. И в вершинах помечается, выделен ли данный блок кому-то.

Его можно вообще без указателей реализовать в массиве. У блока с номером i два ребенка с номерами 2i+1 и 2i+2.

Можно вообще битовый массив использовать для пометок.