Задать вопрос
mrjbom
@mrjbom
алгоритмы

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

Нужно реализовать Buddy аллокатор памяти, но не могу понять, какой тип бинарного дерева там используется, вроде как AVL, так ли это? И можно-ли где-то взять хорошую реализацию этого дерева на Си, дабы не писать велосипед?
  • Вопрос задан
  • 45 просмотров
Комментировать
Подписаться 1 Простой Комментировать
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Нет, там не AVL дерево. Там просто полное дерево из всех блоков. Фиксированное. И в вершинах помечается, выделен ли данный блок кому-то.

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

Можно вообще битовый массив использовать для пометок.
Ответ написан
Комментировать
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы
Вакансии с Хабр Карьеры
С developer (алгоритмист)
СберТех • Москва
от 350 000 ₽
Разработчик WebRTC-сервисов на Go в видеоплатформу
Яндекс • Москва
от 300 000 до 490 000 ₽
С/С++ Linux разработчик
Tempesta Technologies
До 8 000 $
Ещё вакансии
Заказы с Хабр Фриланса
Разработать Custom Speech-to-text Operator на Apache Flink
21 нояб. 2024, в 21:42
100000 руб./за проект
Сделать видио поздравления с субтитрами
21 нояб. 2024, в 21:30
500 руб./за проект
Разработка мобильного приложения с дополненной реальностью (AR)
21 нояб. 2024, в 20:14
200000 руб./за проект
Ещё заказы