Как оформить логику красно-чёрного бинарного дерева? (C++ в частности)
Я не могу найти нормальной литературы, которая объяснила бы мне или подсказала как правильно сделать самобалансирующееся двоичное дерево поиска? К примеру я знаю, что библиотека map сделана на основе такого дерева, так как же работает этот механизм? Если дерево работает на логике (что меньше чем корень дерева, то влево, что больше чем корень дерева, то вправо), то тогда именно это "Меньше" и "Больше" должны быть такими типами данных, которые можно сравнять между собой. А что насчёт строк? Как я могу сравнить что больше: Яблоко или Груша? В map мы задаём ключ к определённому значению. К примеру мы можем легко сделать подобную зависимость : объект_map("Hello") = "Привет". КАК ЭТО РАБОТАЕТ? Является ли слово "Hello" ключом, с помощью которого map итерируется по дереву и находит данные "Привет" за ключом "Hello", или за этим "Hello" стоит число в качестве ключа? Как происходит балансировка дерева? Нам необходимо чтоб с каждой "ветки" шло +- одинаковое количество ветвлений, как научить программу определять эти ветвления, и давать ей команду куда именно запихнуть следующий элемент, при том так, чтоб на это не ушло больше времени, чем нужно компьютеру чтоб определить последний знак числа пи? Может я ОООЧЕНЬ плохо искал, но я не нашёл адекватной информации по этой теме. Мне не нужен код, мне нужен язык логики, слова, или математические формулы, источники, где разжевано что, когда зачем и почему (желательно чтоб понял 11-классник коем я являюсь)
> Как я могу сравнить что больше: Яблоко или Груша?
лексикографически
> Является ли слово "Hello" ключом, с помощью которого map итерируется по дереву и находит данные "Привет" за ключом "Hello", или за этим "Hello" стоит число в качестве ключа?
обычно да, является
если очень хочется ускорить, можешь в своей реализации как бы захешировать первые несколько букв в число для удобства сравнения, но вряд ли это сильно поможет
вообще никто тебе не скажет, как именно в том или ином компиляторе реализован map
всё, что говорится в стандарте - вычислительные сложности для операций map-а (типа "обращение к элементу не медленнее O(log n)"), и то не уверен в этом, а то, как именно реализовывать map, в том числе и мелочи вроде хешировать ли ключи числами или реально всё время сравнивать по буковкам, выбирают разработчики компилятора
если много свободного времени и не жалко психики, можешь почитать исходники какого-нибудь gcc, например, но не думаю, что это сильно поможет в понимании самой структуры
> Как происходит балансировка дерева?
идёшь на вики в статью про сабж, разуваешь глазки и внимательно пролистываешь статью
все случаи балансировки очень подробно расписаны, даже приведены какие-то картинки и примеры кода
> Может я ОООЧЕНЬ плохо искал
да, очень плохо искал
если вообще искал, то хотя бы вики статью найти был должен
По факту у тебя 2 вопроса:
1. Алгоритм поиска.
Поиск происходит по индексам потомков, при этом не важно, какие именно данные хранятся в контейнере, к ним обращаются лишь на этапе сравнения.
Для общего понимания известных алгоритмов посмотри приложение http://algorithm.wiki/
2. Контейнер map из STL.
Этот контейнер тебе не очень подходит для данной задачи, поскольку не имеет индексов (порядка объектов). Hello в твоем примере действительно является ключом для доступа к данным.
Посмотри этот курс для лучшего понимания.