придуманные китайским школьником

4.2 же, внимательнее читать-то надо

внимательнее читать-то надо

Что ты хотел сказать? Chen Quifeng придумал size balanced trees, похожие на weight-balanced trees, но с несколько иными условиями и правилами балансировки. Сейчас этот школьник - уже студент, и собирается переезжать в США, защищать там в будущем диссертацию.

Chen Quifeng придумал size balanced trees

Что ты «пейсатель»... Сорт оф прув:

Seems this concept (size-balanced binary search tree) is no new. See:

Stephen Adams, «Efficient sets: a balancing act», Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB.

--------

I am Chen Qifeng, the author of that paper. First I have to say «I never say that this concept, „Size Balanced“ , is created by myself and that it is faster than all existing BSTs». I think the new in my paper is the unique way to keep balanced:i

Первая ссылка из гугла.

Seems this concept (size-balanced binary search tree) is no new. See:

Школьник не разобрался в определениях.
Та страничка, которую он приводит, называется: «Weight balanced binary trees»: http://groups.csail.mit.edu/mac/users/adams/BB/
Это деревья, в которых тоже есть «rotate» и «double rotate», так же определяется вес вершины. Но это не _size_ balanced trees.
Повторяю - у школьника другие условия и правила балансировки. Другие деревья.

P.S.
У китайского школьника, кстати, операция DeleteNode была недоделана, а исходник вообще GNU Pascal Compiler не смог откомпилировать. Поэтому пришлось переписать всё полностью (только для Maintain взял его алгоритм).

То, что ты привел - это обычное variant weight-balanced tree, похоже ещё из глюками.
См. работу японцев Youchi Hirai и Kazuhiko Yamamoto: http://hagi.is.s.u-tokyo.ac.jp/~yh/bst.pdf
У них найден баг в стандартной балансировке этих variant weight-balanced trees (см. страницу 292 их статьи - «4 Balancing bugs in the variant WBT»).

У китайского школьника же - другой термин - size-balanced :)
И совершенно другие правила балансировки.

LeftRotate

Вижу, что вам лень смотреть код на GitHub, привожу сорцы здесь:

int SBT_LeftRotate(TNodeIndex t) {

        if (t < 0) return 0;
        TNodeIndex k = _nodes[t].right;
        if (k < 0) return 0;
        TNodeIndex p = _nodes[t].parent;

        // поворачиваем ребро дерева
        _nodes[t].right = _nodes[k].left;
        _nodes[k].left = t;

        // корректируем size
        _nodes[k].size = _nodes[t].size;
        TNodeIndex n_l = _nodes[t].left;
        TNodeIndex n_r = _nodes[t].right;
        TNodeSize s_l = ((n_l != -1) ? _nodes[n_l].size : 0);
        TNodeSize s_r = ((n_r != -1) ? _nodes[n_r].size : 0);
        _nodes[t].size = s_l + s_r + 1;

        // меняем трёх предков
        // 1. t.right.parent = t
        // 2. k.parent = t.parent
        // 3. t.parent = k
        if (_nodes[t].right != -1) _nodes[_nodes[t].right].parent = t;
        _nodes[k].parent = p;
        _nodes[t].parent = k;

        // меняем корень, parent -> t, k
        if (p == -1) _tree_root = k; // это root
        else {
                if (_nodes[p].left == t) _nodes[p].left = k;
                else _nodes[p].right = k; // вторую проверку можно не делать
        }
        return 1;
}

Maintain

int SBT_Maintain_Simpler(TNodeIndex t, int flag) {

        if (t < 0) return 0;
        TNodeIndex parent = _nodes[t].parent; // есть "родитель"
        int at_left = 0;
        if (parent == -1) { // t - корень дерева, он изменяется; запоминать нужно не индекс, а "топологию"
        }
        else {
            if (_nodes[parent].left == t) at_left = 1; // "слева" от родителя - индекс родителя не изменился
            else at_left = 0; // "справа" от родителя
        }

        // поместили слева, flag == 0
        if (flag == 0) {
                if (SBT_Left_Left_size(t) > SBT_Right_size(t)) {
                        SBT_RightRotate(t);
                }
                else if (SBT_Left_Right_size(t) > SBT_Right_size(t)) {
                        SBT_LeftRotate(_nodes[t].left);
                        SBT_RightRotate(t);
                }
                else { return 0; }
        }
        // поместили справа, flag == 1
        else {
                if (SBT_Right_Right_size(t) > SBT_Left_size(t)) {
                        SBT_LeftRotate(t);
                }
                else if (SBT_Right_Left_size(t) > SBT_Left_size(t)) {
                        SBT_RightRotate(_nodes[t].right);
                        SBT_LeftRotate(t);
                }
                else { return 0; }
        }

        TNodeIndex t0 = -1;
        if (parent == -1) t0 = _tree_root;
        else {
            if (at_left) t0 = _nodes[parent].left;
            else t0 = _nodes[parent].right;
        }
        SBT_Maintain_Simpler(_nodes[t0].left, 0); // false
        SBT_Maintain_Simpler(_nodes[t0].right, 1); // true
        SBT_Maintain_Simpler(t0, 0); // false
        SBT_Maintain_Simpler(t0, 1); // true

        return 0;
}

Что можете сказать о возможных способах оптимизации этих функций? Я вижу, что в Maintain можно «развернуть» рекурсию. Для оптимизации ассемблерного кода я пока слабоват (не изучал современные методы оптимизации). Суть использования функции Maintain, что мы как и в случае AVL-балансировки (после Add/Delete) - проходим по поддереву вверх, до корня дерева - log(N).

«Weight balanced binary trees»

Такого в названию нету). Или ткните.

И здесь: http://www.mew.org/~kazu/proj/weight-balanced-tree/ пишут:

In 1991, Adams created a variant of weight balanced tree for the programming competition organized by Appel. Its weight is purely «size». He defined (delta,gamma) = (3 or larger, 1) in his SML implementations and papers. The pair (delta,gamma) of «wttree.scm» is (5,1).

Про баг есть (кстати исправили в 2010). Вооще-то я и полагал, что size-balanced - вариант wbt. (Хотя подозреваю, что сия терминология возможно не общепринятая).

Так же в сорцах Data.Set этот вариант называется size-balanced:

-- The implementation of 'Set' is based on /size balanced/ binary trees (or -- trees of /bounded balance/) as described by: -- -- * Stephen Adams, \«/Efficient sets: a balancing act/\», -- Journal of Functional Programming 3(4):553-562, October 1993, -- <http://www.swiss.ai.mit.edu/~adams/BB/>.

// хм, надо будет все-таки алгоритм китайца посмотреть (если будет не влом)

хм, надо будет все-таки алгоритм китайца посмотреть (если будет не влом)

TITLE html-документа http://www.swiss.ai.mit.edu/~adams/BB/- говорит про «Weight balanced ...».
К тому же, термин size balanced в гугле почти не встречается в других работах (я сделал этот вывод из первых двух страниц гугля по запросу для SBT).

Я боюсь только, что в алгоритмах китайца для Add и Delete придется разворачивать рекурсию (в Delete я её развернул, осталось в Add).

Так же в сорцах Data.Set этот вариант называется size-balanced

Хм-хм. Какие сорцы - наиболее понятно описывают алгоритм weight-balanced trees? GNU Scheme, Haskell? Похоже, это будет более быстрая имплементация для ассоциативного массива, чем у китайца.

TITLE html-документа

А... у меня плохо видно, но он менее показателен, его же не автор может задать.

Какие сорцы - наиболее понятно описывают алгоритм weight-balanced trees?

Схему не видел, и там может оставаться баг, а хаскель... Модуль ведь низкоуровневый, и оптимизаций много:

http://www.haskell.org/ghc/docs/latest/html/libraries/containers/src/Data-Set...

Лучше в hugs смотреть Set.hs (только проверить наличие бага, асимптотика по идее должна быть та же).

Зачем тебе _lock_nodes? Он нигде не используется. А если возникнет необходимость в его использовании, то пусть этот мьютекс определяется на стороне клиента, а не либины.

И да, переменные 'l_l', 'q' — это прелесть, абсолютно говорящие названия.

Респект за работу, респект за OpenSource, но код, как в подавляющем большинстве свободных проектов, ужасен; лично для меня.

Зачем тебе _lock_nodes?

Не использую. Оставил чисто для напоминания, что надо как-то
обходить глобальные блокировки на дерево при вставке. В случае, если доступ будет из нескольких потоков.

И да, переменные 'l_l', 'q' — это прелесть

Для математика такие обозначения естественны.

Для математика такие обозначения естественны.

А ты уверен, что твоей библиотекой (раз выложил для всеобщего пользования) будут пользоваться только математики? А вот вдруг придется дебажить в поисках странного поведения? Привыкай делать код ЧИТАЕМЫМ, а не доступным узкому кругу специалистов.

будут пользоваться только математики?

Там же всё разжёвано в каталоге doc/sbt.pdf :)
Не нравится код - перепиши.
Не можешь переписать - используй то, что дают.

Расскажу секрет. Документация имеет свойство теряться. Особенно в Open Source проектах. Особенно, если эту библиотек заюзал разработчик, неговорящий на великом и могучем: зачем ему pdf с непонятной кириллицей? Взял и выкинул.

Я не буду называть тебя говнокодером, я просто посоветую прочитать (перечитать?) книгу МакКонелла, не пропустив соответствующую именованию переменных главу.

Я не буду называть тебя говнокодером, я просто посоветую прочитать (перечитать?) книгу МакКонелла

Это не надо делать. У всех людей мышление разное.
Я уже на своём веку видел много «гуру». :)
Моё отличие от них - что я более культурен, и не так эмоционален.

И да, переменные 'l_l', 'q' — это прелесть, абсолютно говорящие названия.

Кому надо - заменит названия. Я пишу так, как пишут математики.

Ты лучше вот что скажи ...
Реально ли отказаться при работе с деревом от parent-связей (т.е. от двусвязности структуры)?
Просто с parent - работать очень удобно. Я даже не представляю сейчас, как переделать только на left+right -связи.

pacify

Реально ли отказаться при работе с деревом от parent-связей (т.е. от двусвязности структуры)?
Просто с parent - работать очень удобно. Я даже не представляю сейчас, как переделать только на left+right -связи.

а в чём проблема? Зачем вам эта parent связь? Двигаться вверх по дереву? Но ведь вы двигаетесь вверх только _после_ того, как прошли вниз, т.е. после обработки поддерева вы выходите из рекурсивной функции обработки, и как раз и оказываетесь в родительском узле. В итоге, для одно операции например вставки вам нужно спустится на нужный лист, а потом подняться тем же путём (спускаемся во время поиска, поднимаемся для балансировки). В итоге поддержка parent это лишняя трата памяти и времени (т.к. при вращении узлов вам нужно ещё и parent корректировать). Единственное, зачем эта связь нужна - это для итераторов, для них придётся иметь для каждого итератора свой отдельный стек. Однако, ИМХО это более экономично.

Мне такой способ показался приемлемым (в моем случае это имъютэбл a-b дерево). При вставке ключа, рекурсивно спускаюсь вниз, в поисках подходящей позиции. При прохождении каждого parent-узла, кладу его в список. Оказываясь в нужном узле - вставляю ключ, и обратно до корня, двигаюсь разматывая список. Возможно Вам(pacify) стоит приглядеться к zipper http://www.haskell.org/haskellwiki/Zipper

smap

При вставке ключа, рекурсивно спускаюсь вниз, в поисках подходящей позиции. При прохождении каждого parent-узла, кладу его в список. Оказываясь в нужном узле - вставляю ключ, и обратно до корня, двигаюсь разматывая список.

а какой в этом смысл, если при входе в рекурсию такой список всё равно создаётся автоматически, и практически не отнимает ресурсов?

Вы на стек намекаете? Иначе я не понял как и какой список создается автоматически. Поясните пожалуйста.

smap

Вы на стек намекаете?

да, конечно. И не намекаю, а прямо об этом пишу: смысл делать список для возврата назад, если такой список мы УЖЕ получили, когда двигались вперёд? Для деревьев это очень удобно ещё и потому, что мы можем неявно хранить в стеке ещё и дополнительную информацию о родительском узле, которая нам нужна была во время спуска вниз. Например мы можем обрабатывать отдельно левые и отдельно правые узлы, двумя отдельными вызовами одной рекурсивной функции. Тогда при выходе из рекурсии, мы УЖЕ будем знать, левый это узел, или правый.

Теперь ясно, спасибо. Но, у меня реализовано через хвостовую рекурсию. Эксперементально выяснил что оверфлоу случится уже при высоте дерева в 3 тысячи. Хоть такой «громадный» объем информации в моем случае мало вероятен(напомню, у меня b-tree, например возьмем 2-4 дерево), все же не стал ограничиваться глубиной рекурсии.

smap

Эксперементально выяснил что оверфлоу случится уже при высоте дерева в 3 тысячи. Хоть такой «громадный» объем информации в моем случае мало вероятен(напомню, у меня b-tree, например возьмем 2-4 дерево), все же не стал ограничиваться глубиной рекурсии.

высота дерева растёт пропорционально логарифму числа узлов. Логарифм по основанию 2 от 1 099 511 627 776 равен всего 40. Ну ладно, дерево у вас не совсем сбалансировано, пусть не 40, а всего 100. Всё равно - это мелочи. Ваши 3 тыщи, это где-то так 1230231922161117176931558813276752514640713895736833715766118029160058800614672948775360067838593459582429649254051804908512884180898236823585082482065348331234959350355845017413023320111360666922624728239756880416434478315693675013413090757208690376793296658810662941824493488451726505303712916005346747908623702673480919353936813105736620402352744776903840477883651100322409301983488363802930540482487909763484098253940728685132044408863734754271212592471778643949486688511721051561970432780747454823776808464180697103083861812184348565522740195796682622205511845512080552010310050255801589349645928001133745474220715013683413907542779063759833876101354235184245096670042160720629411581502371248008430447184842098610320580417992206662247328722122088513643683907670360209162653670641130936997002170500675501374723998766005827579300723253474890612250135171889174899079911291512399773872178519018229989376 узлов, если у вас хватило на них памяти, то как не хватает на стек?

ладно, давай еще раз. При высоте дерева 0 max количество узлов 1, при высоте 1(в 2-4 дереве) max количество узлов 4, при высоте 2 max количество узлов 16, при высоте 3 max количество узлов 64 и т.д. Допустим нужно вставить ключ k. Сколько родительских узлов нужно пройти до подходящего узла при высоте дерева h, где h=3?

smap

Допустим нужно вставить ключ k. Сколько родительских узлов нужно пройти до подходящего узла при высоте дерева h, где h=3?

1. как доказал Кнут, любое дерево можно привести к бинарному (например 2-3 дерево эквивалентно красно-чёрному). Потому, для простоты давай рассматривать только бинарные.
2. практически всегда дерево НЕ сбалансировано, потому «высота» - понятие расплывчатое. Есть минимальная высота, есть максимальная. В AVL дереве минимальная высота может быть на 1 меньше максимальной, в красно-чёрном максимальная высота может быть вдвое больше минимальной. В любом случае, на практике применяются деревья, в которых _максимальная_ высота растёт как O(log(N)), гда N - число узлов.
3. из п2 и п3 следует, что в _любом_ дереве нам потребуется пройти O(log(N)) узлов, что-бы добраться до нужного узла. Т.е. если h_max=3, и дерево двоичное, то в нём не может быть более 2^3==8 узлов, однако, дойти до листа можно максимум за 3 шага. Если у тебя максимум 64 узла, то следовательно, h_max для эквивалентного бинарного дерева равно 6, и нам потребуется максимум 6 проверок, результат каждой из которых равен 1 или 0.
4. в 2-4 дереве ничего не меняется: высота равна трём, но и проверки более сложные - больше вариантов. Нетрудно доказать, что для перехода к нужному листу нам потребуется выполнить ровно столько же работы, как и в случае бинарного дерева (строгое доказательство см. у Кнута).

Из всего этого следует, что если дерево хоть как-то сбалансировано (h_max ~= O(log(N))), то при h_max = 3000, число узлов у нас будет exp(3000), т.е. какое-то число в степени 3000. ИЧСХ, для упомянутого 2-4 дерева, основание степени будет не меньше двух, а следовательно число узлов будет не меньше 2^3000. Даже если каждый узел занимает 1 байт(что невозможно, ибо там должно быть как минимум два указателя на любой из 2^3000 узлов, плюс уникальное число над полем в 2^3000 значений, т.е. одного байта явно не хватит), то всё равно, для хранения этих всех узлов не хватит ВСЕХ накопителей информации в этом Мире.

На практике, даже при h_max == 40, счёт уже идёт на десятки гигов, а при чуть больших значениях уже нет смысла ничего считать.

Очевидные вещи глаголишь, которые сидят в подсознании. Но из виду как-то упустил величину t^h, t<=2 - это степень, раз мы условились рассматривать бинарные деревья для простоты. Так что спасибо за дискуссию и хорошие ответы. Пересмотрю некоторые решения относительно реализации функционала в своей библиотеки.

На практике, даже при h_max == 40, счёт уже идёт на десятки гигов,

Всё правильно говоришь.

Кстати, я решил избавиться от рекурсии, развернув её в циклы.

smap

Но из виду как-то упустил величину t^h, t<=2 - это степень

да, действительно. Однако IRL это не играет особой роли, если размер стека пропорционален O(log(N)), и константа пропорциональности не слишком велика (а с чего она будет велика? даже для красно-чёрного дерева эта константа равна 2 в самом худшем случае. Т.е. на миллиард узлов достаточно 80 рекурсий(а не 40, как по моей формуле)).

pacify

я решил избавиться от рекурсии, развернув её в циклы.

зачем? структура данных (дерево) рекурсивная, значит и структура программы должна быть рекурсивной. Ведь все алгоритмы тоже рекурсивные, смысл их разворачивать? Стек всё равно будет более экономичным решением. Только надо все действительно временные переменные оформить как static в области видимости данной функции. А то они тоже будут сохраняться в стеке, если объявлять их как автоматические.