Database Reference
In-Depth Information
Figure A1-4b.
Graphic Representation of a Binary Tree
A1.2.3 Application of Binary Trees
Binary trees are typically applied in the following ways:
•
Binary trees (and extensions of binary trees) are used extensively
in database management systems (DBMS) and operating system
(OS) construction to effectively manage indexes of data files.
•
Binary trees are used in calculation of expressions during
compilation.
•
Binary trees are used in data compressions, example, Huffman
Coding Tree.
A1.2.4 Operations on Binary Trees
The following are the main operations that are normally defined on a binary tree:
•
Creation:
At creation the tree either has no nodes or a dedicated
root-node.
•
Insertion:
We may allow insertion at the root, after terminal
nodes only, or we may allow insertion anywhere in tree.
•
Deletion:
Again, we may allow deletion of terminal nodes only,
or we may allow deletion of nodes from anywhere in tree.
•
Clear:
Remove all nodes from the binary tree, thus leaving it empty.
•
Check-Size:
Return the size of the tree.
•
Check-Empty:
Check if the tree is empty.
•
In-order:
In-order traversal of the tree.
•
Pre-order:
Pre-order traversal of the tree.
•
Post-order:
Post-order traversal of the tree.
