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; }
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
Structures and data processing algorithms.
Terms: Structures and data processing algorithms.