Дерево без рекурсии

В этой статье я покажу двоичное дерево без рекурсии. Я думаю что оно в некоторых случаях будет более удобно, нежели дерево с рекурсией.

Итак, начнем. Допустим есть задачка, получить много данных и вывести совпадения. Я нашел одно решение с рекурсией в интернете и понял как это сделать просто. Мне понравилось это решение, но мы знаем что рекурсия заполняет стек и если будет большая вложенность, то будет много выходов из функций. Я захотел попробовать сделать такой алгоритм, который не нуждается в рекурсии. Я буду писать на 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 миллионов, но возможно, что алгоритм, который я буду использовать, привел в этой статье, возможно будет даже лучше рекурсивной функции. Но для этого надо произвести расчёты, которые я только учусь делать.

Я поменял статью, дерево теперь сбалансированное.

Всем спасибо за внимание.