You get a bonus - 1 coin for daily activity. Now you have 1 coin

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 2 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.


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Structures and data processing algorithms.

Terms: Structures and data processing algorithms.