Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,039
1

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

06.04.2013, 18:40. Просмотров 966. Ответов 6
Метки нет (Все метки)

Здорова!
Нужно вообщем построить дерево, токо не обычное дерево, а "красно чорное".
Я начитал литературы, даже видео нашол
http://www.youtube.com/watch?f... DHFF4wjWYU
но нигде нету примера кода.
Да и видео заполнения дерева меня вообще запутало.
Я так понял "красно чорное" дерево от обычного бинарного дерева отличается лишь способом добавления элементов ну и лишним полем флагом красное или чорное.
Значит мне нужно как нибудь написать функцию для заполнения.
Помогите новичку!
Да и вообще как узлы меняются фиг проссыш.
Помогите разобраться кто шарит!

Добавлено через 5 минут
ППц я его вручную не могу построить не то что программу написать
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.04.2013, 18:40
Ответы с готовыми решениями:

Класс "Красно черные деревья"
Народ,нужен доступно-понятный класс КЧД,желательно с определенными методами вращений,добавления...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно"
В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло",...

Для каждой строки найти слова, которые не имеют ни одного из букв: "l", "k", "r", "s" i "j"
Задано символьные строки. Строка состоит из нескольких слов (наборов символов), которые разделяются...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование)
Разработать программу с использованием наследования классов, реализующую классы: − воин;...

6
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
06.04.2013, 19:46 2
Цитата Сообщение от ninja2 Посмотреть сообщение
Я так понял "красно чорное" дерево от обычного бинарного дерева отличается лишь способом добавления элементов ну и лишним полем флагом красное или чорное.
это поверхностные отличия. основное отличие состоит в том, что RB-tree растет вверх, в отличие от BST (которое растет вниз). В RB-tree высота черных узлов одинакова для левого и правого поддеревьев любого узла, и увеличивается она только при перекраске обоих дочерних узлов корня.

Это самое основное. Лучше вам почитать про него у Кормена (есть алгоритмы на псевдокоде для поиска, вставки и удаления узлов) или Седжвика (есть реализация на c++ для поиска и вставки, все остальное в виде упражнений; надо поднапрячься, чтобы их решить). Подходы к реализации у авторов немного отличаются.
0
12 / 12 / 0
Регистрация: 08.04.2012
Сообщений: 81
06.04.2013, 21:11 3
*чЕрное
http://ru.wikipedia.org/wiki/Красно-чёрное_дерево
Читай, там вполне адекватно все расписано.
0
380 / 351 / 113
Регистрация: 17.05.2012
Сообщений: 1,049
06.04.2013, 23:00 4
ninja2, мне кажется, если найти хорошо написанный псевдокод, то все станет понятно, но я пока сам не нашел...
0
1346 / 986 / 312
Регистрация: 28.07.2012
Сообщений: 2,743
06.04.2013, 23:06 5
ninja2, в книге Кормена "Алгоритмы: Построение и анализ" есть отличное описание обычных деревьев, красно-черных деревьев, их отличий от обычных, а также псевдокод к методам. Так что дерзай.
0
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,039
07.04.2013, 00:58  [ТС] 6
Я обычные знаю как строить. Щас наверно построю обычное и функцию которая будет печатать дерево и показывать куда какой элемент попадает, а потом буду пытаться строить функцию добавления, чтобы элементы вставлялись в дерево как на видео. Я думаю щас вручную на листе бумаги потренируюсь заполнять "красно черное" дерево, выделю алгоритм, а затем спокойно построю функцию добавления. Так наверно и сделаю. Ток щас освижу в памяти обычное бинарное дерево.

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

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

Добавлено через 1 минуту
Да и по работе с указателями навыки улучшу.
0
380 / 351 / 113
Регистрация: 17.05.2012
Сообщений: 1,049
07.04.2013, 09:06 7
ninja2, ну я бинарное писал по псевдокоду, и это помогло мне разобраться

Добавлено через 1 минуту
ninja2, т.е. сначала написал что как должно идти на бумаге, а потом уже писал код
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.04.2013, 09:06

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания"
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс"
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об...

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления"
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс...

Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата"
определить тип данных запись имеющий поля фамилия пол зарплата. определить массив из 10 записей. в...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.