Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Поиск в красно-черном дереве - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ задание с вектором http://www.cyberforum.ru/cpp-beginners/thread321318.html
//напишите программу, где создается вектор из 10 элементов. При помощи итератора присвойте //каждому элементу значение, которое вдвое больше его текущего значения #include <iostream> #include...
C++ Вещественные значения функций Люди добрые подскажите что означает вещественное значение функцийЧто такое обьясните. не могу решить задачу не поняв ее всем спасибо заранее http://www.cyberforum.ru/cpp-beginners/thread321310.html
C++ Организация ввода и вывода одномерных массивов в турбо С
При поступлении в вуз абитуриенты, получившие двойку на первом экзамене, ко второму не допускаются. В массиве A записаны оценки экзаменующихся, полученные на первом экзамене. Подсчитать, сколько...
Сортировка индексов алгоритмом std::sort C++
Есть два массива одинаковой размерности. В одном хоть что, во втором целые числа (индексы элементов первого массива). Нужно выполнить сортировку второго массива по заданным полям первого массива....
C++ Сортировка массива с указанием направления http://www.cyberforum.ru/cpp-beginners/thread321263.html
Здравствуйте еще раз! Есть массив отсортированный пузырьком. В функцию SortArr надо добавить третий параметр - указатель на шаблонную функцию определения направления сортировки. Можно сортировать ...
C++ блок while Каким блоком позначается в С++ оператор while? подробнее

Показать сообщение отдельно
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772

Поиск в красно-черном дереве - C++

17.06.2011, 12:11. Просмотров 2019. Ответов 15
Метки (Все метки)

Доброе утро! Изучая, Стандарт выполняю задание - создайте шаблон ассоциативного контейнера.
В общем он будет предельно прост, лишь с одним публичным оператором [].
Предлагается сделать его на основе красно черного дерева. Прочитав про дерево пришел к выводу, что при добавлении элемента в контейнер он сравнивается на предмет больше или меньше с теми, что уже в контейнере. Потом добавляется в нужное место и далее правятся цвета узлов.
1. подскажите от чего отталкиваться при сравнении элементов? Ведь ключ может быть чем угодно, строкой, символом, цифрой, указателем, объектом пользователя. что взять за основу? Первое, что пришло в голову это делать сравнение полагаясь на то, что ключ это char* и не морочиться, но хотелось бы понимания, ведь map принимает ключом, что угодно(так?), и работает с ними. Подозреваю, что в map есть несколько специализаций, но это не проливает свет на общий механизм сравнения.
2. Цвет. Долго пользовал некую инет приладу на java, иллюстрирующую работу красно черного дерева.
Все там вроде хорошо, но...нарушется правило потомки черного - 2 красных и наоборот. Со временем при добавлении узлов, там начинается черное черное. Ну и в качестве метода сравнения - цифры. Закралось подозрение - что то не так. Вопрос. Сохранение комбинации цветов - это принципиально или этим можно поступится в угоду соблюдения остальных правил дерева?

Добавлено через 14 минут
3. наверное самое важное - это поиск в дереве. пусть например строки. есть строка на входе и есть такая же глубоко в дереве. как пройти к ней? ведь используя больше меньше можно уйти совсем не туда. а перебирать все узлы по указателям - это мягко говоря не тянет на скоростной поиск в ассоциативных контейнерах

Добавлено через 1 час 8 минут
про цвета я нагородил. черный черный может быть. а в остальном пока непонятно
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru