2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Задача на красно-черное дерево
Сообщение15.04.2015, 13:49 


19/12/13
9
Давайте рассмотрим: кчд такое, что в его вершинках лежат натуральные числа [1..n], найти возможные значения ключа в корне.

Пытался вывести через рекуренты, но получил разнос.

 Профиль  
                  
 
 Re: Задача на красно-черное дерево
Сообщение17.04.2015, 17:22 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
Вам бы это открыть в математике.
Да, я видел, что Вас там уже закрыли. Так надо же было в математической формулировке.

 Профиль  
                  
 
 Re: Задача на красно-черное дерево
Сообщение17.04.2015, 17:36 
Заслуженный участник


04/05/09
4582
Я бы сначала установил диапазон количества возможных элементов в КЧ дереве определённой глубины (количество чёрных узлов в любом пути к листьям). Очевидно любое количество элементов из этого диапазона реализуемо, что позволяет построить неравенства на количества элементов в левом и правом поддеревьях корня.

 Профиль  
                  
 
 Re: Задача на красно-черное дерево
Сообщение24.04.2015, 22:27 


26/06/14
83
Множество возможных значений ключа в корне дерева имеет вид [a , b] (докажите сами).

Задача сводится к поиску левой и правой границы этого диапазона. То есть: нужно взять максимально разбалансированное дерево из N элементов, вычислить число элементов с одной из сторон и вычесть что-то из N.

Вместо N нужно взять N округлённое вверх до ближайшего возможного числа узлов в максимально разбалансированном дереве.

Поправьте меня, если я в чём-то неправ.

 Профиль  
                  
 
 Re: Задача на красно-черное дерево
Сообщение27.04.2015, 10:48 


19/12/13
9
Тут без вопросов, что будет промежуток.

А вот получение минимума или максимума из промежутка, уже интереснее. Собственно, именно этот вопрос меня и поставил в тупик.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group