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

@ninja2 · Регистрация: 26.09.2012

Студворк — интернет-сервис помощи студентам

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

Добавлено через 5 минут
ППц я его вручную не могу построить не то что программу написать

@ya_noob · 06.04.2013, 19:46

Сообщение от ninja2

Я так понял "красно чорное" дерево от обычного бинарного дерева отличается лишь способом добавления элементов ну и лишним полем флагом красное или чорное.

это поверхностные отличия. основное отличие состоит в том, что RB-tree растет вверх, в отличие от BST (которое растет вниз). В RB-tree высота черных узлов одинакова для левого и правого поддеревьев любого узла, и увеличивается она только при перекраске обоих дочерних узлов корня.

Это самое основное. Лучше вам почитать про него у Кормена (есть алгоритмы на псевдокоде для поиска, вставки и удаления узлов) или Седжвика (есть реализация на c++ для поиска и вставки, все остальное в виде упражнений; надо поднапрячься, чтобы их решить). Подходы к реализации у авторов немного отличаются.

@RussDragon · 06.04.2013, 21:11

*чЕрное
http://ru.wikipedia.org/wiki/Красно-чёрное_дерево
Читай, там вполне адекватно все расписано.

@yoghurt92 · 06.04.2013, 23:00

ninja2, мне кажется, если найти хорошо написанный псевдокод, то все станет понятно, но я пока сам не нашел...

@nonedark2008 · 06.04.2013, 23:06

ninja2, в книге Кормена "Алгоритмы: Построение и анализ" есть отличное описание обычных деревьев, красно-черных деревьев, их отличий от обычных, а также псевдокод к методам. Так что дерзай.

@ninja2 · 07.04.2013, 00:58 **[ТС]**

Я обычные знаю как строить. Щас наверно построю обычное и функцию которая будет печатать дерево и показывать куда какой элемент попадает, а потом буду пытаться строить функцию добавления, чтобы элементы вставлялись в дерево как на видео. Я думаю щас вручную на листе бумаги потренируюсь заполнять "красно черное" дерево, выделю алгоритм, а затем спокойно построю функцию добавления. Так наверно и сделаю. Ток щас освижу в памяти обычное бинарное дерево.

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

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

Добавлено через 1 минуту
Да и по работе с указателями навыки улучшу.

@yoghurt92 · 07.04.2013, 09:06

ninja2, ну я бинарное писал по псевдокоду, и это помогло мне разобраться

Добавлено через 1 минуту
ninja2, т.е. сначала написал что как должно идти на бумаге, а потом уже писал код

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@ninja2 979 / 196 / 33 Регистрация: 26.09.2012 Сообщений: 2,041

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

@RussDragon 12 / 12 / 0 Регистрация: 08.04.2012 Сообщений: 81
	06.04.2013, 21:11
	*чЕрное http://ru.wikipedia.org/wiki/Красно-чёрное_дерево Читай, там вполне адекватно все расписано. 0

@yoghurt92 381 / 352 / 113 Регистрация: 17.05.2012 Сообщений: 1,049
	06.04.2013, 23:00
	ninja2, мне кажется, если найти хорошо написанный псевдокод, то все станет понятно, но я пока сам не нашел... 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	06.04.2013, 23:06
	ninja2, в книге Кормена "Алгоритмы: Построение и анализ" есть отличное описание обычных деревьев, красно-черных деревьев, их отличий от обычных, а также псевдокод к методам. Так что дерзай. 0

@ninja2 979 / 196 / 33 Регистрация: 26.09.2012 Сообщений: 2,041
	07.04.2013, 00:58 [ТС]
	Я обычные знаю как строить. Щас наверно построю обычное и функцию которая будет печатать дерево и показывать куда какой элемент попадает, а потом буду пытаться строить функцию добавления, чтобы элементы вставлялись в дерево как на видео. Я думаю щас вручную на листе бумаги потренируюсь заполнять "красно черное" дерево, выделю алгоритм, а затем спокойно построю функцию добавления. Так наверно и сделаю. Ток щас освижу в памяти обычное бинарное дерево. Добавлено через 24 секунды Да отличия там не большие, токо в функции добавления. Добавлено через 2 минуты yoghurt92, Оно мб и знать как оно строиться и нафиг не нада хз. Да скорее всего и не нужно. Фиг оно кода пригодится. Ну все рамно помучаюсь наверно, попрактикуюсь в С++, лишним не будет. А мб и будет, ну фиг сним ахота просто самому построить. На видео нравиться как оно прикольно заполняется. Добавлено через 1 минуту Да и по работе с указателями навыки улучшу. 0

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