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

"красно чорные" деревья - C++

Восстановить пароль Регистрация
 
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
06.04.2013, 18:40     "красно чорные" деревья #1
Здорова!
Нужно вообщем построить дерево, токо не обычное дерево, а "красно чорное".
Я начитал литературы, даже видео нашол
http://www.youtube.com/watch?feature...&v=vDHFF4wjWYU
но нигде нету примера кода.
Да и видео заполнения дерева меня вообще запутало.
Я так понял "красно чорное" дерево от обычного бинарного дерева отличается лишь способом добавления элементов ну и лишним полем флагом красное или чорное.
Значит мне нужно как нибудь написать функцию для заполнения.
Помогите новичку!
Да и вообще как узлы меняются фиг проссыш.
Помогите разобраться кто шарит!

Добавлено через 5 минут
ППц я его вручную не могу построить не то что программу написать
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.04.2013, 18:40     "красно чорные" деревья
Посмотрите здесь:

C++ Необработанное исключение в "0x00412b4a" в "kursovik.exe": 0xC0000005: Нарушение прав доступа при чтении "0x00000004".
Необработанное исключение в "0x00414558" в "467.exe": 0xC0000005: Нарушение прав доступа при чтении "0xabababbb" C++
Необработанное исключение в "0x775e15de" в "laba3.exe": 0xC0000005: Нарушение прав доступа при чтении "0xfdfdfdf9". C++
C++ Необработанное исключение в "0x01082855" в "sort.exe": 0xC0000005: Нарушение прав доступа при записи "0xcccccccc"
Необработанное исключение в "0x778e15de" в "dir-3.exe": 0xC0000005: Нарушение прав доступа при чтении "0x00000000" C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
06.04.2013, 19:46     "красно чорные" деревья #2
Цитата Сообщение от ninja2 Посмотреть сообщение
Я так понял "красно чорное" дерево от обычного бинарного дерева отличается лишь способом добавления элементов ну и лишним полем флагом красное или чорное.
это поверхностные отличия. основное отличие состоит в том, что RB-tree растет вверх, в отличие от BST (которое растет вниз). В RB-tree высота черных узлов одинакова для левого и правого поддеревьев любого узла, и увеличивается она только при перекраске обоих дочерних узлов корня.

Это самое основное. Лучше вам почитать про него у Кормена (есть алгоритмы на псевдокоде для поиска, вставки и удаления узлов) или Седжвика (есть реализация на c++ для поиска и вставки, все остальное в виде упражнений; надо поднапрячься, чтобы их решить). Подходы к реализации у авторов немного отличаются.
RussDragon
 Аватар для RussDragon
12 / 12 / 1
Регистрация: 08.04.2012
Сообщений: 81
06.04.2013, 21:11     "красно чорные" деревья #3
*чЕрное
http://ru.wikipedia.org/wiki/Красно-чёрное_дерево
Читай, там вполне адекватно все расписано.
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
06.04.2013, 23:00     "красно чорные" деревья #4
ninja2, мне кажется, если найти хорошо написанный псевдокод, то все станет понятно, но я пока сам не нашел...
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,340
06.04.2013, 23:06     "красно чорные" деревья #5
ninja2, в книге Кормена "Алгоритмы: Построение и анализ" есть отличное описание обычных деревьев, красно-черных деревьев, их отличий от обычных, а также псевдокод к методам. Так что дерзай.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
07.04.2013, 00:58  [ТС]     "красно чорные" деревья #6
Я обычные знаю как строить. Щас наверно построю обычное и функцию которая будет печатать дерево и показывать куда какой элемент попадает, а потом буду пытаться строить функцию добавления, чтобы элементы вставлялись в дерево как на видео. Я думаю щас вручную на листе бумаги потренируюсь заполнять "красно черное" дерево, выделю алгоритм, а затем спокойно построю функцию добавления. Так наверно и сделаю. Ток щас освижу в памяти обычное бинарное дерево.

Добавлено через 24 секунды
Да отличия там не большие, токо в функции добавления.

Добавлено через 2 минуты
yoghurt92, Оно мб и знать как оно строиться и нафиг не нада хз. Да скорее всего и не нужно. Фиг оно кода пригодится. Ну все рамно помучаюсь наверно, попрактикуюсь в С++, лишним не будет. А мб и будет, ну фиг сним ахота просто самому построить. На видео нравиться как оно прикольно заполняется.

Добавлено через 1 минуту
Да и по работе с указателями навыки улучшу.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.04.2013, 09:06     "красно чорные" деревья
Еще ссылки по теме:

C++ Красно-черные деревья C++
C++ Необработанное исключение в "0x013f2b22" в "123.exe": 0xC0000005: Нарушение прав доступа при записи "0xfdfdfdfd"
C++ Класс "Красно черные деревья"

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

Или воспользуйтесь поиском по форуму:
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
07.04.2013, 09:06     "красно чорные" деревья #7
ninja2, ну я бинарное писал по псевдокоду, и это помогло мне разобраться

Добавлено через 1 минуту
ninja2, т.е. сначала написал что как должно идти на бумаге, а потом уже писал код
Yandex
Объявления
07.04.2013, 09:06     "красно чорные" деревья
Ответ Создать тему
Опции темы

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