Tree without recursion
In this article, I will show you a binary tree without recursion. I think that in some cases it will be more convenient than a tree with recursion.
So, let’s begin. Let’s say you have a problem, get a lot of data and display matches. I found one solution on the Internet and I figured out how to do it simply. I liked this solution, but we know that recursion fills the stack and if there is a lot of nesting, there will be many exits from functions. I wanted to try to make an algorithm that doesn’t need recursion. I will write in C because it is a language that everyone can understand.
The first step is to define the structure.
struct node {
unsigned long number;
unsigned long count;
unsigned long step;
struct node *parent;
struct node *left;
struct node *right;
};Here number is the number by which the node will be sorted. Count is the number of matches. Step will be needed to output matches to the console, it will determine whether there was an entry into this node or not.
We make a global link to the root of the tree.
struct node *root;Now we add our function for inserting numbers, it looks a little different – for example, now, unlike the recursive function, it does not require the address of the structure.
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;
}
}
}I’ve specified local variables as registers to make it a little faster. If you look through the disassembler, you can see that the 64-bit processor has enough registers.
[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
Now the addition occurs without recursion. Next, you need to walk through the tree and see if there are any matches. This is also possible without recursion. Here is the code.
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: %ldn", 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;
}
}Yes, it looks like much more than a recursive function, but that is the price to implement the search in one loop. I used the step variable to determine where the pointer was already and where it wasn’t.
Now check out the complete code.
#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: %ldn", 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: %ldn", 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);
}In general, I have not seen problems with a recursive function for a million elements or 10 million, but it is possible that the algorithm I will use, given in this article, may be even better than a recursive function. But for this it is necessary to make calculations, which I am just learning to do.
Thank you all for your attention.
