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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.67
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
17.06.2011, 12:11     Поиск в красно-черном дереве #1
Доброе утро! Изучая, Стандарт выполняю задание - создайте шаблон ассоциативного контейнера.
В общем он будет предельно прост, лишь с одним публичным оператором [].
Предлагается сделать его на основе красно черного дерева. Прочитав про дерево пришел к выводу, что при добавлении элемента в контейнер он сравнивается на предмет больше или меньше с теми, что уже в контейнере. Потом добавляется в нужное место и далее правятся цвета узлов.
1. подскажите от чего отталкиваться при сравнении элементов? Ведь ключ может быть чем угодно, строкой, символом, цифрой, указателем, объектом пользователя. что взять за основу? Первое, что пришло в голову это делать сравнение полагаясь на то, что ключ это char* и не морочиться, но хотелось бы понимания, ведь map принимает ключом, что угодно(так?), и работает с ними. Подозреваю, что в map есть несколько специализаций, но это не проливает свет на общий механизм сравнения.
2. Цвет. Долго пользовал некую инет приладу на java, иллюстрирующую работу красно черного дерева.
Все там вроде хорошо, но...нарушется правило потомки черного - 2 красных и наоборот. Со временем при добавлении узлов, там начинается черное черное. Ну и в качестве метода сравнения - цифры. Закралось подозрение - что то не так. Вопрос. Сохранение комбинации цветов - это принципиально или этим можно поступится в угоду соблюдения остальных правил дерева?

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

Добавлено через 1 час 8 минут
про цвета я нагородил. черный черный может быть. а в остальном пока непонятно
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
17.06.2011, 12:26     Поиск в красно-черном дереве #2
Цитата Сообщение от AzaKendler Посмотреть сообщение
на основе красно черного дерева.
А что это такое?
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
17.06.2011, 12:45  [ТС]     Поиск в красно-черном дереве #3
taras atavin, неловкая ситуация(. красно черное дерево - условное обозначение структуры хранения данных в памяти, разновидность древовидной структуры + используется цвет узлов для пущего порядка. например список - это цепочка узлов, узел имеет 2 указателя на соседей или один.
У любого дерева думается мне минимум 3 указателя - один на предыдущий узел 2 на следующие. Вот так сказать своими словами, насколько сам понял

Добавлено через 2 минуты
http://ru.wikipedia.org/wiki/%D0%A4%...ee_example.svg
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
17.06.2011, 13:04     Поиск в красно-черном дереве #4
1. Если правильно понял вопрос, то можно позволить пользователю опционально передавать функцию/объект для сравнения ключа. А по умолчанию передавать std::less<T>, как во многих контейнерах стандартной библиотеки шаблонов.
3. Поиск должен производиться по правилам двоичного дерева поиска

Цитата Сообщение от AzaKendler Посмотреть сообщение
У любого дерева думается мне минимум 3 указателя - один на предыдущий узел 2 на следующие.
В общем случае ссылка на предыдущий узел не обязательна.
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
17.06.2011, 13:06     Поиск в красно-черном дереве #5
AzaKendler, вот пример с произвольной функцией сравнения (см. шаблонный параметр comp): Бинарные деревья для двоичного дерева поиска (несбалансированного). Там же есть и поиск.
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
17.06.2011, 14:14  [ТС]     Поиск в красно-черном дереве #6
Nameless One, супер. только готовые решения(((как то сразу отбивают желание ваять и тренироваться. (не у меня, все равно считаю необходимым реализовать самому, пусть это будет уродливо, но по другому никак не научиться)
Возник вопрос, а зачем Node делать тоже шаблоном? можно эту структуру сделать вложенной и чтоб у нее были просто члены Т* left. Или это невыгодно? В чем плюс шаблонного нод?

Добавлено через 3 минуты
читал что из шаблона генерится только то что пользуется. но нод вроде бы используется все время и будет генериться и в случае шаблона и в случае вложения. Я могу просто чего то не знать, подскажи плиз в чем выгода
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
17.06.2011, 14:46     Поиск в красно-черном дереве #7
Цитата Сообщение от AzaKendler Посмотреть сообщение
Nameless One, супер. только готовые решения
ну дык там не красно-черное дерево. Балансировку тебе придется писать самому.

Цитата Сообщение от AzaKendler Посмотреть сообщение
Возник вопрос, а зачем Node делать тоже шаблоном? можно эту структуру сделать вложенной и чтоб у нее были просто члены Т* left. Или это невыгодно? В чем плюс шаблонного нод?
Разницы никакой, мне просто больше так нравится. А по сути, вложенная структура тоже будет шаблонной. Например, следующие два класса будут взаимозаменяемы:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <class T>
class wrapper1
{
    struct internal
    {
    T value;
    };
 
    internal val;
};
 
template <class T>
class wrapper2
{
    template <class N>
    struct internal
    {
    N value;
    };
 
    internal<T> val;
};
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
17.06.2011, 15:33  [ТС]     Поиск в красно-черном дереве #8
Цитата Сообщение от Nameless One Посмотреть сообщение
В общем случае ссылка на предыдущий узел не обязательна.
а как найти папу без ссылки назад?
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
17.06.2011, 15:41     Поиск в красно-черном дереве #9
AzaKendler, а зачем тебе в двоичном дереве поиска искать папу? Для поиска в дереве нужно иметь возможность реализовать обход от корня к листьям.
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
17.06.2011, 15:47  [ТС]     Поиск в красно-черном дереве #10
Nameless One, просто из той инфы что я читал, балансировка дерева осуществляется с проверкой какого цвета папа, является ли папа вершиной, проверяются так сказать дети папы. Возможно ли это не зная папы?
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
17.06.2011, 17:34     Поиск в красно-черном дереве #11
AzaKendler, почему бы и нет? Ведь до того, как мы делаем балансировку узла, то мы должны еще до него добраться, а это можно сделать только через папу, попутно получая его цвет.
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
17.06.2011, 20:20  [ТС]     Поиск в красно-черном дереве #12
Nameless One,логично но.....помимо этого надо также инфо о дедушке, о втором потомке папы если таковой есть и его цвете,не слишком ли много инфы надо где то хранить по каждому прошедшему узлу взамен простого указателя?

Добавлено через 5 минут
просто мне непонятен момент, зачем где-то собирать еще инфу если каждый узел итак ее содержит, достаточно просто иметь к нему указатель. Я могу и ошибаться...ввиду недостатка опыта.
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
18.06.2011, 00:50     Поиск в красно-черном дереве #13
AzaKendler, я не говорю, что без указателя на родителя будет эффективнее или проще. Я всего лишь ответил на это утверждение:
Цитата Сообщение от AzaKendler Посмотреть сообщение
У любого дерева думается мне минимум 3 указателя - один на предыдущий узел 2 на следующие.
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
18.06.2011, 01:42  [ТС]     Поиск в красно-черном дереве #14
Цитата Сообщение от Nameless One Посмотреть сообщение
AzaKendler, я не говорю, что без указателя на родителя будет эффективнее или проще. Я всего лишь ответил на это утверждение:
ОК, спасибо. Всегда полезно знать варианты, когда они есть
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
18.06.2011, 05:21     Поиск в красно-черном дереве #15
Цитата Сообщение от AzaKendler Посмотреть сообщение
У любого дерева думается мне минимум 3 указателя - один на предыдущий узел 2 на следующие. Вот так сказать своими словами, насколько сам понял
Я не знаю деревьев, чьи узлы имеют указатели на свои предки. И по-моему с таким указателем будет уже не дерево, а граф общего вида.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.06.2011, 11:53     Поиск в красно-черном дереве
Еще ссылки по теме:

C++ Поиск одинаковых элементов в бинарном дереве
Поиск минимальной суммы в дереве C++
C++ NIL в красно-черном дереве

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
18.06.2011, 11:53  [ТС]     Поиск в красно-черном дереве #16
Цитата Сообщение от taras atavin Посмотреть сообщение
Я не знаю деревьев, чьи узлы имеют указатели на свои предки. И по-моему с таким указателем будет уже не дерево, а граф общего вида.


"В пвевдокоде переменные node.llink и node.rlink - указатели на правого и левого сына данного узла; переменная node.parent - указатель на отца данного узла. (При реализации вы можете сохранять указатели на проходимые при движении по дереву узлы (например в стеке!) и таким образом обойтись без указателя на отца, но наличие указателя на отца делает псевдокод значительно проще.)"

http://mathc.chat.ru/a3/articl03.htm

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

Добавлено через 1 минуту
да не смутит фраза псевдокод - просто это первая ссылка которую нашел и воткнул. в ней просто общий смысл

Добавлено через 3 минуты
" В каждом узле типа Node хранятся указатели left, right на двух потомков и parent на предка. Цвет узла хранится в поле color и может быть либо RED, либо BLACK. Собственно данные хранятся в поле data."

вот еще
http://www.codenet.ru/progr/alg/sort_search/rbt.php
Yandex
Объявления
18.06.2011, 11:53     Поиск в красно-черном дереве
Ответ Создать тему
Опции темы

Текущее время: 19:54. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru