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

@AzaKendler · Регистрация: 30.05.2011

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

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

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

Добавлено через 1 час 8 минут
про цвета я нагородил. черный черный может быть. а в остальном пока непонятно

@taras atavin · 17.06.2011, 12:26

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

на основе красно черного дерева.

А что это такое?

@AzaKendler · 17.06.2011, 12:45 **[ТС]**

taras atavin, неловкая ситуация(. красно черное дерево - условное обозначение структуры хранения данных в памяти, разновидность древовидной структуры + используется цвет узлов для пущего порядка. например список - это цепочка узлов, узел имеет 2 указателя на соседей или один.
У любого дерева думается мне минимум 3 указателя - один на предыдущий узел 2 на следующие. Вот так сказать своими словами, насколько сам понял

Добавлено через 2 минуты
http://ru.wikipedia.org/wiki/%... xample.svg

@Nameless One · 17.06.2011, 13:04

1. Если правильно понял вопрос, то можно позволить пользователю опционально передавать функцию/объект для сравнения ключа. А по умолчанию передавать std::less<T>, как во многих контейнерах стандартной библиотеки шаблонов.
3. Поиск должен производиться по правилам двоичного дерева поиска

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

У любого дерева думается мне минимум 3 указателя - один на предыдущий узел 2 на следующие.

В общем случае ссылка на предыдущий узел не обязательна.

@Nameless One · 17.06.2011, 13:06

AzaKendler, вот пример с произвольной функцией сравнения (см. шаблонный параметр comp): https://www.cyberforum.ru/post1696826.html для двоичного дерева поиска (несбалансированного). Там же есть и поиск.

@AzaKendler · 17.06.2011, 14:14 **[ТС]**

Nameless One, супер. только готовые решения(((как то сразу отбивают желание ваять и тренироваться. (не у меня

, все равно считаю необходимым реализовать самому, пусть это будет уродливо, но по другому никак не научиться)
Возник вопрос, а зачем Node делать тоже шаблоном? можно эту структуру сделать вложенной и чтоб у нее были просто члены Т* left. Или это невыгодно? В чем плюс шаблонного нод?

Добавлено через 3 минуты
читал что из шаблона генерится только то что пользуется. но нод вроде бы используется все время и будет генериться и в случае шаблона и в случае вложения. Я могу просто чего то не знать, подскажи плиз в чем выгода

@Nameless One · 17.06.2011, 14:46

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

Nameless One, супер. только готовые решения

ну дык там не красно-черное дерево. Балансировку тебе придется писать самому.

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

Возник вопрос, а зачем Node делать тоже шаблоном? можно эту структуру сделать вложенной и чтоб у нее были просто члены Т* left. Или это невыгодно? В чем плюс шаблонного нод?

Разницы никакой, мне просто больше так нравится. А по сути, вложенная структура тоже будет шаблонной. Например, следующие два класса будут взаимозаменяемы:

C++

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 · 17.06.2011, 15:33 **[ТС]**

Сообщение от Nameless One

В общем случае ссылка на предыдущий узел не обязательна.

а как найти папу без ссылки назад?

@Nameless One · 17.06.2011, 15:41

AzaKendler, а зачем тебе в двоичном дереве поиска искать папу? Для поиска в дереве нужно иметь возможность реализовать обход от корня к листьям.

@AzaKendler · 17.06.2011, 15:47 **[ТС]**

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

@Nameless One · 17.06.2011, 17:34

AzaKendler, почему бы и нет? Ведь до того, как мы делаем балансировку узла, то мы должны еще до него добраться, а это можно сделать только через папу, попутно получая его цвет.

@AzaKendler · 17.06.2011, 20:20 **[ТС]**

Nameless One,логично но.....помимо этого надо также инфо о дедушке, о втором потомке папы если таковой есть и его цвете,не слишком ли много инфы надо где то хранить по каждому прошедшему узлу взамен простого указателя?

Добавлено через 5 минут
просто мне непонятен момент, зачем где-то собирать еще инфу если каждый узел итак ее содержит, достаточно просто иметь к нему указатель. Я могу и ошибаться...ввиду недостатка опыта.

@Nameless One · 18.06.2011, 00:50

AzaKendler, я не говорю, что без указателя на родителя будет эффективнее или проще. Я всего лишь ответил на это утверждение:

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

У любого дерева думается мне минимум 3 указателя - один на предыдущий узел 2 на следующие.

@AzaKendler · 18.06.2011, 01:42 **[ТС]**

Сообщение от Nameless One

AzaKendler, я не говорю, что без указателя на родителя будет эффективнее или проще. Я всего лишь ответил на это утверждение:

ОК, спасибо. Всегда полезно знать варианты, когда они есть

@taras atavin · 18.06.2011, 05:21

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

У любого дерева думается мне минимум 3 указателя - один на предыдущий узел 2 на следующие. Вот так сказать своими словами, насколько сам понял

Я не знаю деревьев, чьи узлы имеют указатели на свои предки. И по-моему с таким указателем будет уже не дерево, а граф общего вида.

@AzaKendler · 18.06.2011, 11:53 **[ТС]**

Сообщение от 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/al... ch/rbt.php

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772
	17.06.2011, 15:47 [ТС]	10
	Nameless One, просто из той инфы что я читал, балансировка дерева осуществляется с проверкой какого цвета папа, является ли папа вершиной, проверяются так сказать дети папы. Возможно ли это не зная папы? 0

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

@taras atavin 4226 / 1795 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	17.06.2011, 12:26	2
	Сообщение от AzaKendler на основе красно черного дерева. А что это такое? 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772
	17.06.2011, 12:45 [ТС]	3
	taras atavin, неловкая ситуация(. красно черное дерево - условное обозначение структуры хранения данных в памяти, разновидность древовидной структуры + используется цвет узлов для пущего порядка. например список - это цепочка узлов, узел имеет 2 указателя на соседей или один. У любого дерева думается мне минимум 3 указателя - один на предыдущий узел 2 на следующие. Вот так сказать своими словами, насколько сам понял Добавлено через 2 минуты http://ru.wikipedia.org/wiki/%... xample.svg 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	17.06.2011, 13:04	4
	1. Если правильно понял вопрос, то можно позволить пользователю опционально передавать функцию/объект для сравнения ключа. А по умолчанию передавать std::less<T>, как во многих контейнерах стандартной библиотеки шаблонов. 3. Поиск должен производиться по правилам двоичного дерева поиска Сообщение от AzaKendler У любого дерева думается мне минимум 3 указателя - один на предыдущий узел 2 на следующие. В общем случае ссылка на предыдущий узел не обязательна. 1

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	17.06.2011, 13:06	5
	AzaKendler, вот пример с произвольной функцией сравнения (см. шаблонный параметр comp): https://www.cyberforum.ru/post1696826.html для двоичного дерева поиска (несбалансированного). Там же есть и поиск. 1

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772
	17.06.2011, 14:14 [ТС]	6
	Nameless One, супер. только готовые решения(((как то сразу отбивают желание ваять и тренироваться. (не у меня, все равно считаю необходимым реализовать самому, пусть это будет уродливо, но по другому никак не научиться) Возник вопрос, а зачем Node делать тоже шаблоном? можно эту структуру сделать вложенной и чтоб у нее были просто члены Т* left. Или это невыгодно? В чем плюс шаблонного нод? Добавлено через 3 минуты читал что из шаблона генерится только то что пользуется. но нод вроде бы используется все время и будет генериться и в случае шаблона и в случае вложения. Я могу просто чего то не знать, подскажи плиз в чем выгода 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772
	17.06.2011, 15:33 [ТС]	8
	Сообщение от Nameless One В общем случае ссылка на предыдущий узел не обязательна. а как найти папу без ссылки назад? 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	17.06.2011, 15:41	9
	AzaKendler, а зачем тебе в двоичном дереве поиска искать папу? Для поиска в дереве нужно иметь возможность реализовать обход от корня к листьям. 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	17.06.2011, 17:34	11
	AzaKendler, почему бы и нет? Ведь до того, как мы делаем балансировку узла, то мы должны еще до него добраться, а это можно сделать только через папу, попутно получая его цвет. 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772
	17.06.2011, 20:20 [ТС]	12
	Nameless One,логично но.....помимо этого надо также инфо о дедушке, о втором потомке папы если таковой есть и его цвете,не слишком ли много инфы надо где то хранить по каждому прошедшему узлу взамен простого указателя? Добавлено через 5 минут просто мне непонятен момент, зачем где-то собирать еще инфу если каждый узел итак ее содержит, достаточно просто иметь к нему указатель. Я могу и ошибаться...ввиду недостатка опыта. 0

	18.06.2011, 11:53

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	18.06.2011, 00:50	13
	AzaKendler, я не говорю, что без указателя на родителя будет эффективнее или проще. Я всего лишь ответил на это утверждение: Сообщение от AzaKendler У любого дерева думается мне минимум 3 указателя - один на предыдущий узел 2 на следующие. 1

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772
	18.06.2011, 01:42 [ТС]	14
	Сообщение от Nameless One AzaKendler, я не говорю, что без указателя на родителя будет эффективнее или проще. Я всего лишь ответил на это утверждение: ОК, спасибо. Всегда полезно знать варианты, когда они есть 0

@taras atavin 4226 / 1795 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	18.06.2011, 05:21	15
	Сообщение от AzaKendler У любого дерева думается мне минимум 3 указателя - один на предыдущий узел 2 на следующие. Вот так сказать своими словами, насколько сам понял Я не знаю деревьев, чьи узлы имеют указатели на свои предки. И по-моему с таким указателем будет уже не дерево, а граф общего вида. 0

@AzaKendler 214 / 116 / 14 Регистрация: 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/al... ch/rbt.php 0