|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
15.05.2013, 16:07 | #1 |
Форумчанин
Регистрация: 07.05.2011
Сообщений: 169
|
Деревья, прям целый лес (сбалансированные и пирамидальные)
Добрый день\вечер, уважаемые программисты!
Вот какие у меня вопросы... ВОПРОС 1 Вообще, мне нужно написать сбалансированное бинарное дерево, (heapsort вроде бы сделала), но пока читала в интерете про сбалансированные, наткнулась на странную вещь. Чтобы сделать дерево, пусть это будет пирамидальная сортировка, нужно взять корень. А потом там сыновей выбирать. А потом их сравнивать, а если что-то не так, то вызывать функцию ещё раз, ещё раз... (т.е., использовать где-то там рекурсию). А я сделала пирамидальную сортировку (надеюсь, что это всё-таки пирамидальная сортировка) без рекурсии. Нашла алгоритм в интернете (псевдокод) и по нему написала алгоритм. Суть алгоритма, что берёшь не с середины корень, а прям с первого элемента. И наращивание на 2*i и 2*i+1. Но у меня нет рекурсии. Я строю из половины массива "дерево", потом "добавляю" в него новые элементы, меняя его с головой, будто бы наращивая размер массива (а по сути, просто двигаюсь по i>n/2). Но отсутствие рекурсии меня, мягко говоря, очень и очень смущает. Может, алгоритм будет не столь эффективным? Вообще, это пирамидальная сортировка? Код:
ВОПРОС 2 Как лучше (и как вообще) реализовать сбалансированное бинарное дерево, если нужно будет ещё написать функции для вставки и удаления элемента? Была бы очень признательна за помощь! Последний раз редактировалось Fanyuus; 15.05.2013 в 16:27. |
15.05.2013, 16:29 | #2 |
Старожил
Регистрация: 31.05.2010
Сообщений: 13,543
|
Я не знаю, кто писал этот бред. Но к "быстрой сортировке" он не имеет никакого отношения.
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder |
15.05.2013, 16:32 | #3 |
Форумчанин
Регистрация: 07.05.2011
Сообщений: 169
|
Smitt&Wesson, ужс :D
*надо срочно переделать хип. |
15.05.2013, 16:35 | #4 | ||||
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,577
|
Прочитал оба вопроса, не пойму как свяазно с темой:
Цитата:
причем тут лес (который множество непересекающихся деревьев) я тоже непонял. дальше читаю внимательно: Цитата:
Цитата:
Цитата:
|
||||
15.05.2013, 16:42 | #5 | ||
Форумчанин
Регистрация: 07.05.2011
Сообщений: 169
|
Цитата:
Курсовая работа. 4-ая задача в 1-ой лабораторной - heapsort, а в 3-ей лабораторной надо написать сбалансированное бинарное дерево. А времени мало. А я тут вдруг увидела, что "нет рекурсии", аж испугалась. *Нашла сейчас на http://algolist.manual.ru/sort/pyramid_sort.php всё, успокоилась, лабораторная норм, а то Smitt&Wesson напугал Цитата:
Последний раз редактировалось Fanyuus; 15.05.2013 в 18:06. |
||
15.05.2013, 17:33 | #6 | |
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,577
|
Цитата:
Но можно выделить память с запасом и хранить где-то количество реально занятых элементов - тогда добавить элемент ты сможешь очень просто. Но когда запас будет исчерпан тебе придеца создавать новый массив (наверное опять с запасом), копировать туда элементы старого массива, а затем, добавлять элемент. (примерно так стандартные вектора работают, т.е. это нормальный ход, с говнокодом при правильном использовании не связанный). Но лучше списки, может быть использовать, да. |
|
15.05.2013, 18:04 | #7 |
Форумчанин
Регистрация: 07.05.2011
Сообщений: 169
|
Пока искала в интернете как добавить и удалить элемент из динамического массива, наткнулась на такую наиползенейшую вещь, как вектор. Он ведь динамический массив, только класс. И удалять умеет. И расширяться по мере необходимости.
Думаю, это отличная идея. потому что до сих пор не поняла работу списков, но желаю летом с этим разобраться)) Теперь у меня вот какой вопрос: Вектор не будет работать медленнее, чем (простой) динамический массив? *Хотя вектор, это и есть динамический массив, только с кучей доп.функций, класс, но... он действительно упростит работу)) Последний раз редактировалось Stilet; 16.05.2013 в 07:53. |
16.05.2013, 06:24 | #8 | |
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,577
|
Цитата:
добавление/удаление элемента в вектор имеет сложность O(N), в список O(1) время произвольного доступа (когда ты пишешь a[34], например) для вектора O(1), для списка O(N) и так далее. В зависимости от того, что там ты будешь с ним делать выбирай между std::list и std::vector |
|
16.05.2013, 16:59 | #9 |
Форумчанин
Регистрация: 07.05.2011
Сообщений: 169
|
rrrFer, а я пока писала свой ответ, читала про эти вектора, соответственно, ваш ответ не видела, но это да - хорошая идея.
Теперь у меня возникли другие вопросы, по поводу сбалансированного дерева. Я уже придумала\нашла связь с "родитель\потомок", реализовать её, думаю, будет не так сложно, это при условии, что массив заполняется по порядку, и 2 условия по поводу "разница не больше одного в уровнях и листах" выполняется преспокойно. Другой вопрос: как бы более корректно реализовать добавление нового элемента и перестраивать всё дерево? В общем, вопрос встал по поводу перестройки дерева и уложения его в известные индексы. Госспади, если я сделаю это сбалансированное дерево, я куплю себе торт от счастья С: |
17.05.2013, 09:30 | #10 | |
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,577
|
Код:
при вставке для балансировки там чето кудато поворачивается, я деталей не помню. мне кажеца я уже предлагал почитать про АВЛ-деревья всякие и красно-черные, ты не реагируешь, я загуглил за тебя (вторая ссылка с гугла: http://algolist.manual.ru/ds/rbtree.php ) и там уже реализовано сбалансированное дерево, бери код и пользуй ) Цитата:
|
|
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
нужно прям сейчас ( элементарно ) | ll0nl1ne | Общие вопросы C/C++ | 12 | 20.12.2011 17:22 |
Графика в TurboPascal: Процедуры, рисующие на экране смешанный лес (лес состоит из елей) по курсору | GreenDay | Помощь студентам | 2 | 04.05.2011 13:31 |
Лес в паскале | GreenDay | Помощь студентам | 2 | 19.04.2011 09:20 |
деревья( | Маргоша1993 | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 10.04.2011 12:38 |