الفهرس 
IntroductionOnly 14 pages are availabe for public view
 |  | from | 16 |  |  |
| | | from | 16 | | |
Abstract
Optimal alphabetic binary trees were designed to handle information of different access frequencies where a symmetric order is imposed on the resulting tree.
Optimal alphabetic trees (OATs) can be build faster than optimal binary search trees, yet they can be used for binary search.
OATs can also be used data compression like Huffman codes; the loss in compression ratio is compensated for be the symmetry of the encoding and decoding process (Huffman codes need an additional hasing mechanism in the decoding).
As for the multi dimensional case, reasonably fast algorithms exist to build a nearly optimal tree. However, in the general case, the optimal tree can only be achieved through dynamic programming.
For the importance and wide range of multi dimensional applications, we start thesis by proposing a new concept ”the expense of a cut” followed by an algorithm for finding the 2-d OAT, experimental results show it is reasonably faster than dynamic programming.
Then we get back to the one dimensional case.
The merits of optimal alphabetic trees are mostly seen by researchers.
The fast implementation to build OATs rather complicated to methods for building other data structures.
In addition, the fact that any editing in the weight sequence may result in the tree losing its optimality, limits the use of OATs in applications of dynamic nature.
This thesis aims to add more flexibility to the processing op OATs opening the door for a wider use of it. We develop linear time (and space) algorithms to insert, delete, or change the weight of a node in an OAT without losing its optimality, to split an OAT into two OATs, and two merge two OATs into one optimal tree.
In addition, we use the linear time merging algorithm to build the tree recursively in a divide and conquer manner; the resulting algorithm is mush simpler, and experimental results show it is also faster, than the existing implementation.
Finally, we introduce similar algorithms to edit the weight sequence of a Huffman tree, since they can be viewed as OATs lacking the proper symmetric order.
Experimental results show the efficiency of the proposed algorithms compared to known methods, except for the merging case.