В этой статье я покажу двоичное дерево без рекурсии. Я думаю что оно в некоторых случаях будет более удобно, нежели дерево с рекурсией.
Итак, начнем. Допустим есть задачка, получить много данных и вывести совпадения. Я нашел одно решение с рекурсией в интернете и понял как это сделать просто. Мне понравилось это решение, но мы знаем что рекурсия заполняет стек и если будет большая вложенность, то будет много выходов из функций. Я захотел попробовать сделать такой алгоритм, который не нуждается в рекурсии. Я буду писать на C, потому что это такой язык, который могут понять все.
Первым делом определим структуру.
struct node {
unsigned long number;
unsigned long count;
unsigned long step;
struct node *parent;
struct node *left;
struct node *right;
};Здесь number это число, по которому будет идти сортировка node. Count это количество совпадений. Step нужен будет для вывода совпадений в консоль, он будет определять, было ли вхождение в этот node или нет.
Делаем глобальную ссылку на корень дерева.
struct node *root;Теперь добавляем нашу функцию по вставке чисел, она выглядит немного по другому - например теперь в отличие от рекурсивной функции, она не требует адрес структуры.
static void add_node (const int number)
{
register struct node *prev = NULL;
register unsigned long left = 0;
register struct node *p = root;
while (1)
{
if (p == NULL)
{
p = calloc (1, sizeof (struct node));
p->number = number;
p->count = 1;
if (prev)
{
if (left) prev->left = p;
else prev->right = p;
p->parent = prev;
}
if (root == NULL)
{
root = p;
p->parent = NULL;
}
return;
}
prev = p;
if (p->number > number)
{
left = 1;
if (p->left && p->number < p->left->number)
{
register struct node *up = p;
register struct node *down = p->left;
p = calloc (1, sizeof (struct node));
p->number = number;
p->count = 1;
p->parent = up;
p->left = down;
return;
}
p = p->left;
} else if (p->number < number)
{
left = 0;
if (p->right && p->number > p->right->number)
{
register struct node *up = p;
register struct node *down = p->right;
p = calloc (1, sizeof (struct node));
p->number = number;
p->count = 1;
p->parent = up;
p->right = down;
return;
}
p = p->right;
} else if (p->number == number)
{
p->count++;
return;
}
}
}
Я указал локальные переменные как регистры, чтобы хоть чуточку быстрее работало. Если посмотреть через дизассемблер, то можно увидеть, что у 64 битного проца хватает регистров.
[0x00401080]> s sym.add_node
[0x00401166]> pd 30
;-- add_node:
0x00401166 55 push rbp
0x00401167 4889e5 mov rbp, rsp
0x0040116a 4155 push r13
0x0040116c 4154 push r12
0x0040116e 53 push rbx
0x0040116f 4883ec18 sub rsp, 0x18
0x00401173 897ddc mov dword [rbp - 0x24], edi
0x00401176 41bc00000000 mov r12d, 0
0x0040117c 41bd00000000 mov r13d, 0
0x00401182 488b1dcf2e00. mov rbx, qword [obj.root] ; [0x404058:8]=0
0x00401189 4885db test rbx, rbx
┌─< 0x0040118c 7559 jne 0x4011e7
Теперь добавление происходит без рекурсии. Далее надо пройтись по дереву и посмотреть есть ли совпадения. Такое тоже возможно не применяя рекурсию. Вот код.
static void find_matches ( )
{
register struct node *n = root;
register nm = 0;
register n->step = 0;
while (n)
{
if (n->step == 0 && n->count > 1)
{
printf ("%ld: %ld\n", n->number, n->count);
nm++;
}
n->step = 1;
if (n->left && n->left->step == 0)
{
n = n->left;
continue;
}
else if (n->right && n->right->step == 0)
{
n = n->right;
continue;
}
else if (n->step == 1)
{
if (n->left) n->left->step = 0;
if (n->right) n->right->step = 0;
n = n->parent;
if (n && n->step == 1 && n->parent == NULL)
{
n->step == 2;
continue;
} else if (!n) break;
}
if (n->step == 1 && n->parent == NULL) break;
}
}Да, она выглядит больше во много чем рекурсивная функция, но это цена за реализацию поиска в одном цикле. Я использовал step переменную, чтобы определять, где уже указатель был, а где не был.
Теперь посмотрите полный код.
static void add_node (const int number)
{
register struct node *prev = NULL;
register unsigned long left = 0;
register struct node *p = root;
while (1)
{
if (p == NULL)
{
p = calloc (1, sizeof (struct node));
p->number = number;
p->count = 1;
if (prev)
{
if (left) prev->left = p;
else prev->right = p;
p->parent = prev;
}
if (root == NULL)
{
root = p;
p->parent = NULL;
}
return;
}
prev = p;
if (p->number > number)
{
left = 1;
if (p->left && p->number < p->left->number)
{
register struct node *up = p;
register struct node *down = p->left;
p = calloc (1, sizeof (struct node));
p->number = number;
p->count = 1;
p->parent = up;
p->left = down;
return;
}
p = p->left;
} else if (p->number < number)
{
left = 0;
if (p->right && p->number > p->right->number)
{
register struct node *up = p;
register struct node *down = p->right;
p = calloc (1, sizeof (struct node));
p->number = number;
p->count = 1;
p->parent = up;
p->right = down;
return;
}
p = p->right;
} else if (p->number == number)
{
p->count++;
return;
}
}
}
В целом я не видел проблем рекурсивной функции на миллион элементов или 10 миллионов, но возможно, что алгоритм, который я буду использовать, привел в этой статье, возможно будет даже лучше рекурсивной функции. Но для этого надо произвести расчёты, которые я только учусь делать.
Я поменял статью, дерево теперь сбалансированное.
Всем спасибо за внимание.
Комментарии (22)
SpiderEkb
21.11.2021 07:45А скиплисты не рассматривали?
https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.524&rep=rep1&type=pdf
Очень эта структура нравится.
Politura
21.11.2021 08:23+11Оно, конечно, полезно пытаться что-то сделать самому, но неплохо-бы еще прокачать оценку своих изысканий и не тащить на хабр откровенно нубский материал.
Проблемы в порядке чтения, а не в порядке важности:
Использование глобальных переменных и статических функций исключительно для того, чтоб избежать передачи лишнего параметра в функцию, мягко говоря, неоправданно.
Дерево не самобалансирующее, а это значит, что на отсортированных данных заполнение дерева даст квадратичную сложность. Ну и на рандомных данных сложность будет гулять от O(n*log(n)) до O(n*n).
Для задачи поиска повторяющихся значений деревья вообще не нужны, можно использовать HashMap у которого сложность добавления и поиска элементов - константа, в результате сложность заполнения мапы будет линейная O(n), а если еще дубли просто класть в HasSet, то проход по всем дублям будет размером с количество оных дублей.
Поиск дублей капец замороченный, прям мозг отказывается читать, ибо надо чуть напрячься, тогда как в нормальном проходе по дереву все ясно с первого взгляда.
С учетом того, что во время поиска в step кладутся либо 0, либо 1, либо 2, есть стойкое подозрение, что на длинных ветках оный поиск просто будет ломаться.
Вообще в рекурсии нет ничего плохого, есть знать, что делаешь.
xverizex Автор
21.11.2021 09:38-7Дерево не самобалансирующее, а это значит, что на отсортированных данных заполнение дерева даст квадратичную сложность. Ну и на рандомных данных сложность будет гулять от O(n*log(n)) до O(n*n).
Вы придумываете проблемы, чтобы придраться чтоли? если данные отсортированы, то мы просто бинарным поиском ищем, если данные как попало поступают, то делаем дерево.
tyomitch
21.11.2021 10:25+3Пусть все данные отсортированы, кроме двух элементов, которые идут в обратном порядке. Как будете искать?
xverizex Автор
21.11.2021 10:09-4я сделал сбалансированное дерево. исправил. можете проверить даже, что всё работает.
tyomitch
21.11.2021 10:21+3Вы уверены, что вы понимаете, что такое «сбалансированное дерево»?
Не вникая в ваш код — вижу, что вrootвсегда остаётся первый добавленный узел. Значит, это не оно.
GospodinKolhoznik
21.11.2021 08:57+3Самое большое преимущество рекурсии, как мне кажется в том, что она позволяет написать аналитический код. Т.е. такой, который можно проанализировать человеческим разумом, логикой и существующим мат. аппаратом.
Тем же преимуществом обладает подход замены "просто цикла" на стандартизированные, предсказуемые и анализируемые сверку, маппинг и фильтр.
А цикл, в котором происходит что то забористое и замороченное плохо поддается анализу. Невозможно предугадать как он себя поведет в том или ином ом случае и какие в нем могут быть скрыты потенциальные баги и проблемы.
qrdl
21.11.2021 09:05+4Я думаю что оно в некоторых случаях будет более удобно, нежели дерево с рекурсией.
В каких случаях? Чем удобнее? Удалось ли подтвердить свое предположение? Непонятен смысл всех этих танцев с бубном.
Я указал локальные переменные как регистры, чтобы хоть чуточку быстрее работало. Если посмотреть через дизассемблер, то можно увидеть, что у 64 битного проца хватает регистров.
Это уже давно не влияет, компилятор сам решает, где ему лучше разместить переменные, так что использовать register смысла нет.
И количество регистров никак не связано с разрядностью проца, если вдруг это подразумевалось.
tyomitch
21.11.2021 09:12+2У x64 вдвое больше регистров общего назначения по сравнению с x86, если вдруг это подразумевалось.
qrdl
21.11.2021 09:17+1Несомненно, но ведь вызвано это отнюдь не увеличением разврядности. Не удивлюсь, если у какого-то древнего 32-битного RISC'а из 90-х (типа IBM POWER2) регистров намного больше, чем у x86_64
А из текста автора может показаться, что разрядность и кол-во регистров - вещи связанные.
xverizex Автор
21.11.2021 09:33-5В каких случаях? Чем удобнее? Удалось ли подтвердить свое предположение? Непонятен смысл всех этих танцев с бубном.
Ну как? Даже Robert Sedgewick пишет в своей книге Algorithms in C, что стек может переполниться. ну вы представляете если у вас 30 000 000 или больше вложений получиться в дереве, какой будет стек? 30 000 000 * 8 = 180 000 000, а тут же ещё память выделенная для данных. Короче я опять думаю что вы не подумав мне написали.
qrdl
21.11.2021 09:54+5Вы считаете все атомы во Вселенной, что у вас 30 млн уровней в двоичном дереве? И если вы имели в виду 30 млн узлов в дереве, то это всего лишь 25 уровней в сбалансированном дереве, значит глубина рекурсии не более 25.
С учетом того, что по AMD64 ABI все параметры и результат передаются в регистрах, локальные переменные скорее всего тоже будут в регистрах, стэк будет использоваться по минимуму.
А хамить не стоит.tyomitch
22.11.2021 08:10+1Добавлю, что атомов во вселенной порядка 2^270, так что миллионы и даже тысячи уровней в дереве не могут быть вообще никогда.
qrdl
21.11.2021 09:58Я задал вопросы, которые, на мой взгляд, должны были быть раскрыты в статье, иначе непонятно, зачем это было писать. Если вы не принимаете конструктивную критику, то не станете лучше писать.
tyomitch
21.11.2021 09:09+7Компилятор сам отлично умеет разворачивать хвостовую рекурсию в цикл (равно как и раскладывать локальные переменные по регистрам). Какой смысл все это расписывать вручную? Автор черпал вдохновение в афоризме Ларри Уолла "Real programmers can write assembly code in any language"?
winwood
21.11.2021 12:33+2У меня вопрос - зачем это делать, если есть стандартная библиотека С++ и на выбор set, multiset, map, multimap, unorderes_set, unorderes_multiset, unorderes_map, unorderes_multimap?
Кроме того, стандартная библиотека шаблонная. А здесь, при смене типа хранимых данных, придется все переписывать.
И еще - чем больше кода, тем больше ошибок. И времени на отладку. Напримерn->step == 2; в функции find_matches. Или calloc без free.
На С++ со стандартными библиотеками это могло выглядеть примерно так:int main(int argc, char **argv)
{
srandom(time(0));
std::map tree;
for (unsigned long i = 0; i < 1000000; i++){
unsigned long r = random () % 1000;
tree[r]++;
}
for (auto e : tree) {
std::cout << e.first << ": " << e.second << std::endl;
}
return 0;
}
AirLight
22.11.2021 04:26Зачем м в узле определять и родителей и потомков? Это не избыточно?
xverizex Автор
22.11.2021 04:36а вы попробуйте без рекурсии пройтись по всем элементам и отобразить их.
tyomitch
22.11.2021 08:05Вместо того, чтобы тратить O(log n) дополнительной памяти на хранение пути от корня до текущего узла, предлагаете тратить O(n) дополнительной памяти на хранение родителя каждого узла?
ubunifu
Nested sets часто используется в крупных магазинах, смысл не только в том что можно от рекурсии избавится, а к примеру получить дерево одним запросом
SELECT id, name, step FROM category_tree ORDER BY left
В итоге, после небольшой обработки (в которой step играет роль множителя отступа), получим следующий список: