Representation of a sparse array as a binary tree using the example of the C language

Lecture

In essence, a binary tree is simply a modified doubly linked list. Its main advantage is the ability to quickly search. Due to this, it is possible to very quickly perform inserts and spend quite a bit of time on access to the elements. (After all, binary trees are ideal for applications that require a linked list structure in which the search should take very little time.)

To use a binary tree to implement a spreadsheet, you need to change the cell structure as follows:

  struct cell {
   char cell_name [9];  / * cell name, eg A1, B34 * /
   char formula [128];  / * data, eg, 10 / B2 * /
   struct cell * left;  / * pointer to the left subtree * /
   struct cell * right;  / * pointer to the right subtree * /
 } list_entry;

The street () function in Chapter 22 can be modified to build a tree based on the cell name. The following code assumes that the parameter n is a pointer to an inserted tree element.

  struct cell * stree (
         struct cell * root,
         struct cell * r,
         struct cell * n)
 {
   if (! r) {/ * first vertex of the subtree * /
     n-> left = NULL;
     n-> right = NULL;
     if (! root) return n;  / * first entrance to the tree * /
     if (strcmp (n-> cell_name, root-> cell_name) <0)
       root-> left = n;
     else
       root-> right = n;
     return n;
   }

   if (strcmp (r-> cell_name, n-> cell_name) <= 0)
     stree (r, r-> right, n);
   else
     stree (r, r-> left, n);

   return root;
 }

When calling the stree () function, it needs to pass pointers to the root of the tree as the first two parameters and a pointer to the new cell as the third. The function returns a pointer to the root.

To delete a cell of a spreadsheet, you can use the modified dtree () function shown below, which takes the cell name as a key:

  struct cell * dtree (
         struct cell * root,
         char * key)
 {
   struct cell * p, * p2;

   if (! root) return root;  / * item not found * /

   if (! strcmp (root-> cell_name, key)) {/ * root removal * /
     / * it means an empty tree * /
     if (root-> left == root-> right) {
       free (root);
       return NULL;
     }
     / * or if one of the subtrees is empty * /
     else if (root-> left == NULL) {
       p = root-> right;
       free (root);
       return p;
     }
     else if (root-> right == NULL) {
       p = root-> left;
       free (root);
       return p;
     }
     / * or if both subtrees are non-empty * /
     else {
       p2 = root-> right;
       p = root-> right;
       while (p-> left) p = p-> left;
       p-> left = root-> left;
       free (root);
       return p2;
     }
   }
   if (strcmp (root-> cell_name, key) <= 0)
     root-> right = dtree (root-> right, key);
   else root-> left = dtree (root-> left, key);
   return root;
 }

Finally, to quickly find a cell in a spreadsheet by its name, you can use a modified version of the search () function.

  struct cell * search_tree (
         struct cell * root,
         char * key)
 {
   if (! root) return root;  / * empty tree * /
   while (strcmp (root-> cell_name, key)) {
     if (strcmp (root-> cell_name, key) <= 0)
       root = root-> right;
     else root = root-> left;
     if (root == NULL) break;
   }
   return root;
 }

Analysis of the method of representation in the form of a binary tree

Using a binary tree significantly reduces the time to insert and search for items compared to a linked list. It should be remembered that sequential search requires on average n / 2 comparisons, where n is the number of list items. Compared to this, a binary search requires only log ₂ n comparisons (if the tree is balanced). In addition, binary trees also use memory as economically as linked lists. However, in some situations there are better alternatives than binary trees.