BST

Оптимизированная реализация дерева бинарного поиска на C++.

Внимание: Дерево бинарного поиска по определению не является сбалансированным, то есть это дерево не гарантирует асимптотическую сложность O(log n) при поиске или при удалении элементов.

Что особенного в этой реализации?

  • Достаточно хорошо оптимизирована по сравнению с другими реализациями в Интернете.
  • Полностью отсутствует рекурсия. (Кроме обхода дерева при отладочном выводе)
  • Отсутствуют лишние вызовы функций - логика функций непосредственно находится в теле соответствующих методов класса. Поиск, удаление элементов построены полностью на циклах.
  • Поддерживается возможность выборочного извлечения либо самого правого потомка из левого поддерева, либо самого левого потомка из правого поддерева при удалении элемента с обеими сыновьями, что даёт возможность поддерживать условный “баланс” при многократном удалении. (Эту возможность легко модифицировать или убрать, если вам она не нужна).
  • Добавление уникальных / не уникальных элементов.
  • Поддерживаются 2 метода удаления элементов:
    1. С подменой удаляемого узла и копированием полезной нагрузки (эффективно, когда размер полезной нагрузки меньше чем 2 * sizeof(void*)).
    2. С перенастройкой указателей.
  • Реализовано с помощью шаблонов C++.
  • Метод для отладочного вывода дерева в визуально-понятном виде, с отступами.
  • Легковесная, один заголовочный файл.

Copyright © 2019 Александр Майоров. Все права защищены.