Сортирующее дерево, пирамида, куча. Нахождение позиции при вставке узла!

[FasterHarder]

Всем хай!
Сразу к делу!

Есть сортирующее дерево. Ключи - целые числа. Дерево является максимальным, т е макс.значение содержится в корневом узле.
Хочется окончательно понять, как находить позицию при вставке узла в дерево. Т е не сам алгоритм пузырькового подъема (bubble up), а именно, где находится позиция ЗА последним элементов в сорт.дереве. Ведь алгоритмически при добавлении узла он вставляется в конец дерева и начинается подниматься вверх, до тех пор, пока не будут выполняться свойства пирамиды (в моем случае: отец больше своих сыновей).

На картинке представлены два состояния пирамиды (полная и почти полная). Хотелось бы иметь универсальный алгоритм нахождения позиции за последним элементов в сорт.дереве.
Сразу скажу, что пирамида НЕ отражается на одномерном массиве. Т е из структур данных в наличии ТОЛЬКО сортирующее дерево и ничего более!

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

Как правильно находить позицию ЗА последним элементов в сорт.дереве?

P.S. В С++ в STL это значение итератора, возвращаемого end() - ссылка на виртуальный элемент, стоящий за последним в контейнере, но которого нет физически в коллекции

Прикреплённая картинка

[Славян]

Если у вас есть n=количество узлов уже существующего дерева (или ваш вариант-указат. на только что добавленный), то можно определить слой/высоту, на кой добавлять узел придётся: log₂n (в примере №1 [log₂11]=3), смещение в этом слое, и уже за O(log(n)) приземлиться на прогнозируемое место.

Добавлено 05.03.17, 14:17
Описочка. Так надо: "на кой добавлять узел придётся: log₂(n+1)".

[amk]

Эти деревья реализуются не посредством указателей а над вектором. Так что вставка осуществляется на первую свободную позицию, после чего производится подъём.

[AVA12]

Да тут все очевидно.

Сначала по количеству узлов определяем глубину нового узла (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).

[FasterHarder]

Цитата amk @ 05.03.17, 15:58

Эти деревья реализуются не посредством указателей а над вектором. Так что вставка осуществляется на первую свободную позицию, после чего производится подъём.

Пирамида имеет несколько вариантов реализаций!
Можно иметь узел с ТРЕМЯ указателями (на левого сына, на правую дочь и на прямого отца).
Я же специально написал, что сорт.дерево НЕ отображается на векторе...

И речь не о том, что более эффективно, а что нет. У меня совсем др. цель и менять структуру данных нельзя!

[OpenGL]

Цитата FasterHarder @ 05.03.17, 16:22

Я же специально написал, что сорт.дерево НЕ отображается на векторе...

И речь не о том, что более эффективно, а что нет. У меня совсем др. цель и менять структуру данных нельзя!

Звучит как "у меня есть микроскоп, и мне надо забить гвоздь. Молоток брать нельзя!". Двоичная куча легко и непринуждённо представляется в виде массива, и задача, где было бы удобнее иное представление, в голову не приходит. Может скажешь, что ты решаешь изначально?

[amk]

FasterHarder, может тебе надо по дереву спуститься к узлу с заданным номером?

Метод прост - если пронумеровать узлы послойно начиная с 1 (№1 в корне, №2 в корне левого поддерева, №3 в корне правого поддерева и т.д.), то, чтобы добраться до вершины №N, берём двоичное представление числа N, отбрасываем левую "1", и, стартуя в корне, спускаемся влево, если очередная цифра "0", и вправо, если "1". Когда цифры кончатся, указатель будет указывать на нужную вершину.

[FasterHarder]

Цитата OpenGL @ 06.03.17, 14:18

Может скажешь, что ты решаешь изначально?

В 1-ом посте треда написано, какую задачу я решаю!
Повторю еще раз! "Как правильно находить позицию ЗА последним элементов в сорт.дереве?" Ты видишь в постановке слово "массив"? Нет? Я тоже.

Цитата amk @ 06.03.17, 15:11

Метод прост - если пронумеровать узлы послойно начиная с 1 (№1 в корне, №2 в корне левого поддерева, №3 в корне правого поддерева и т.д.)

чтобы пронумеровать узлы дерева, дерево к этому моменту ДОЛЖНО быть построено. А проблема в том, что для построения дерева нужно УМЕТЬ вставлять в него узел. В этом вся и проблема!

AVA12
примерно суть понятна

[OpenGL]

Цитата FasterHarder @ 14.03.17, 20:06

Повторю еще раз! "Как правильно находить позицию ЗА последним элементов в сорт.дереве?" Ты видишь в постановке слово "массив"? Нет? Я тоже.

То есть тебя не смущает, что ты забиваешь гводи микроскопом? Ок, тогда нормальное решение - приклеить к микроскопу молоток и бить так, чтобы удар наносился молотком. Иными словами - построить параллельно дереву массив, все операции производить на нём и постоянно их синхронизировать с деревом.

[amk]

Цитата FasterHarder @ 14.03.17, 20:06

для построения дерева нужно УМЕТЬ вставлять в него узел. В этом вся и проблема!

Нет там никакой проблемы. Не можешь составить алгоритм, попробуй построить дерево вручную. При этом фиксируй свои действия, и главное , запоминай, что тебе для выполнения этой работы по пути понадобилось.