Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.21.34.0] |
|
Сообщ.
#1
,
|
|
|
Всем хай!
Сразу к делу! Есть сортирующее дерево. Ключи - целые числа. Дерево является максимальным, т е макс.значение содержится в корневом узле. Хочется окончательно понять, как находить позицию при вставке узла в дерево. Т е не сам алгоритм пузырькового подъема (bubble up), а именно, где находится позиция ЗА последним элементов в сорт.дереве. Ведь алгоритмически при добавлении узла он вставляется в конец дерева и начинается подниматься вверх, до тех пор, пока не будут выполняться свойства пирамиды (в моем случае: отец больше своих сыновей). На картинке представлены два состояния пирамиды (полная и почти полная). Хотелось бы иметь универсальный алгоритм нахождения позиции за последним элементов в сорт.дереве. Сразу скажу, что пирамида НЕ отражается на одномерном массиве. Т е из структур данных в наличии ТОЛЬКО сортирующее дерево и ничего более! Может иметь какой-нибудь глобальный указатель, на только что добавленный элемент, но это вроде не сильно помогает в определении местоположения для вставки след.узла. Как правильно находить позицию ЗА последним элементов в сорт.дереве? P.S. В С++ в STL это значение итератора, возвращаемого end() - ссылка на виртуальный элемент, стоящий за последним в контейнере, но которого нет физически в коллекции Прикреплённая картинка
|
Сообщ.
#2
,
|
|
|
Если у вас есть n=количество узлов уже существующего дерева (или ваш вариант-указат. на только что добавленный), то можно определить слой/высоту, на кой добавлять узел придётся: log2n (в примере №1 [log211]=3), смещение в этом слое, и уже за O(log(n)) приземлиться на прогнозируемое место.
Добавлено Описочка. Так надо: "на кой добавлять узел придётся: log2(n+1)". |
Сообщ.
#3
,
|
|
|
Эти деревья реализуются не посредством указателей а над вектором. Так что вставка осуществляется на первую свободную позицию, после чего производится подъём.
|
Сообщ.
#4
,
|
|
|
Да тут все очевидно.
Сначала по количеству узлов определяем глубину нового узла (d, 0 для корня) и локальный индекс (k) нового узла на нижнем уровне. Если делать тупо в лоб, то можно последовательно вычитать из общего количества количество узлов на очередном уровне (2^i, для корня i = 0), пока возможно. Количество итераций даст d, а остаток - k. Ну или умнее - прибавить к количеству узлов единицу и обнулить старший единичный бит - индекс обнуленного бита будет d, а итог - k. Для первого примера получаем d = 3, k = 3, для второго d = 4, k = 0. Запоминаем k и интервал возможных индексов для уровня d (для первого примера - 0..7). Последовательно спускаемся из корня, по индексу и интервалу определяем, влево идти или вправо, после каждой итерации оставляем от интервала только соответствующую половину. Например: - исходный интервал 0..7, k = 3; k принадлежит к левой половине интервала, т. ч. идем влево; - интервал 0..3, k принадлежит к правой половине - идем вправо; - интервал 2..3, k принадлежит к правой половине - идем вправо; - от интервала остался один элемент - мы на месте. Или умнее: оставить от k ровно d бит (включая незначащие), затем перебирать эти биты от старшего к младшему и идти влево (если 0) или вправо (если 1). |
Сообщ.
#5
,
|
|
|
Цитата amk @ Эти деревья реализуются не посредством указателей а над вектором. Так что вставка осуществляется на первую свободную позицию, после чего производится подъём. Пирамида имеет несколько вариантов реализаций! Можно иметь узел с ТРЕМЯ указателями (на левого сына, на правую дочь и на прямого отца). Я же специально написал, что сорт.дерево НЕ отображается на векторе... И речь не о том, что более эффективно, а что нет. У меня совсем др. цель и менять структуру данных нельзя! |
Сообщ.
#6
,
|
|
|
Цитата FasterHarder @ Я же специально написал, что сорт.дерево НЕ отображается на векторе... И речь не о том, что более эффективно, а что нет. У меня совсем др. цель и менять структуру данных нельзя! Звучит как "у меня есть микроскоп, и мне надо забить гвоздь. Молоток брать нельзя!". Двоичная куча легко и непринуждённо представляется в виде массива, и задача, где было бы удобнее иное представление, в голову не приходит. Может скажешь, что ты решаешь изначально? |
Сообщ.
#7
,
|
|
|
FasterHarder, может тебе надо по дереву спуститься к узлу с заданным номером?
Метод прост - если пронумеровать узлы послойно начиная с 1 (№1 в корне, №2 в корне левого поддерева, №3 в корне правого поддерева и т.д.), то, чтобы добраться до вершины №N, берём двоичное представление числа N, отбрасываем левую "1", и, стартуя в корне, спускаемся влево, если очередная цифра "0", и вправо, если "1". Когда цифры кончатся, указатель будет указывать на нужную вершину. |
Сообщ.
#8
,
|
|
|
Цитата OpenGL @ Может скажешь, что ты решаешь изначально? В 1-ом посте треда написано, какую задачу я решаю! Повторю еще раз! "Как правильно находить позицию ЗА последним элементов в сорт.дереве?" Ты видишь в постановке слово "массив"? Нет? Я тоже. Цитата amk @ Метод прост - если пронумеровать узлы послойно начиная с 1 (№1 в корне, №2 в корне левого поддерева, №3 в корне правого поддерева и т.д.) чтобы пронумеровать узлы дерева, дерево к этому моменту ДОЛЖНО быть построено. А проблема в том, что для построения дерева нужно УМЕТЬ вставлять в него узел. В этом вся и проблема! AVA12 примерно суть понятна |
Сообщ.
#9
,
|
|
|
Цитата FasterHarder @ Повторю еще раз! "Как правильно находить позицию ЗА последним элементов в сорт.дереве?" Ты видишь в постановке слово "массив"? Нет? Я тоже. То есть тебя не смущает, что ты забиваешь гводи микроскопом? Ок, тогда нормальное решение - приклеить к микроскопу молоток и бить так, чтобы удар наносился молотком. Иными словами - построить параллельно дереву массив, все операции производить на нём и постоянно их синхронизировать с деревом. |
Сообщ.
#10
,
|
|
|
Цитата FasterHarder @ Нет там никакой проблемы. Не можешь составить алгоритм, попробуй построить дерево вручную. При этом фиксируй свои действия, и главное , запоминай, что тебе для выполнения этой работы по пути понадобилось. для построения дерева нужно УМЕТЬ вставлять в него узел. В этом вся и проблема! |