~ 549 день👨‍💻 | Двоичные деревья поиска

Сегодня изучал двоичные деревья поиска (бинарные деревья).

Бывают:
- полными (full binary tree);
- строгими (strictly binary tree);
- законченными (complete binary tree);

Бинарные деревья обеспечивают быстрый поиск данных за O(log n).

Отличия от обычных деревьев, которые я изучал накануне:
1) данные в дереве хранятся в определённом порядке;
2) поиск выполняется с учётом этого порядка;

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

Допускается реализация с хранением узлов с одинаковыми ключами. Тогда действует правило: ключ правого потомка должен быть больше или равен ключу родителя. Подобные деревья называют частично упорядоченными.

------
Реализовал структуру данных и покрыл тестами.
Осталось реализовать метод удаления узла.

С кодом можно ознакомиться по ссылке на гитхаб:
https://github.com/avagners/algorithms_and_data_structures/tree/main/data_structures/binary_search_trees

📚Чтение:
+ 14 стр. "Изучаем SQL" Алан Бьюли (2007 год)
(135 страниц из 308)