В этой статье я покажу двоичное дерево без рекурсии. Я думаю что оно в некоторых случаях будет более удобно, нежели дерево с рекурсией.
Итак, начнем. Допустим есть задачка, получить много данных и вывести совпадения. Я нашел одно решение в интернете и понял как это сделать просто. Мне понравилось это решение, но мы знаем что рекурсия заполняет стек и если будет большая вложенность, то будет много выходов из функций. Я захотел попробовать сделать такой алгоритм, который не нуждается в рекурсии. Я буду писать на 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;
p = p->left;
} else if (p->number < number)
{
left = 0;
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 переменную, чтобы определять, где уже указатель был, а где не был.
Теперь посмотрите полный код.
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
struct node {
unsigned long number;
unsigned long count;
unsigned long step;
struct node *parent;
struct node *left;
struct node *right;
};
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;
p = p->left;
} else if (p->number < number)
{
left = 0;
p = p->right;
} else if (p->number == number)
{
p->count++;
return;
}
}
}
static int nm = 0;
static int nr = 0;
static void find_matches ( )
{
struct node *n = root;
nm = 0;
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;
}
}
static void recursive_find (struct node *n)
{
if (n)
{
if (n->count > 1)
{
printf ("%ld: %ld\n", n->number, n->count);
nr++;
}
recursive_find (n->left);
recursive_find (n->right);
}
}
int main (int argc, char **argv)
{
srandom (time (0));
for (unsigned long i = 0; i < 1000000; i++)
{
unsigned long r = random () % 1000;
add_node (r);
}
find_matches ( );
//recursive_find (root);
}В целом я не видел проблем рекурсивной функции на миллион элементов или 10 миллионов, но возможно, что алгоритм, который я буду использовать, привел в этой статье, возможно будет даже лучше рекурсивной функции. Но для этого надо произвести расчёты, которые я только учусь делать.
Всем спасибо за внимание.
