Mastering Algorithms With C - Kyle Loudon [81]
Traversal methods
Techniques for visiting the nodes of a tree in a specific order. Because the nodes of a tree are organized in a hierarchical fashion, there are several options for traversing them.
Tree balancing
A process used to keep a tree as short as possible for a given number of nodes. This is especially important in search trees, wherein height influences the overall performance of the tree a great deal.
Binary search trees
Binary trees organized specifically for searching. Binary search trees are good for searching data in which we expect to perform insertions and deletions.
Rotations
Methods for keeping binary search trees balanced. Specifically, this chapter explores AVL rotations, the rotations applied to AVL (Adel'son-Vel'skii and Landis) trees. An AVL tree is one type of balanced binary search tree.
Some applications of trees are:
Huffman coding
A method of data compression that uses a Huffman tree to compress a set of data (see Chapter 14). A Huffman tree is a binary tree that determines the best way to assign codes to symbols in the data. Symbols occurring frequently are assigned short codes, whereas symbols occurring less frequently are assigned longer ones.
User interfaces
Examples are graphical user interfaces and interfaces to file systems. In graphical user interfaces, windows take on a hierarchical arrangement forming a tree. Every window, except the top-level window, has one parent from which it is started, and each window may have several children launched from it. Directories in hierarchical file systems have a similar organization.
Database systems
In particular, those that require both efficient sequential and random access while performing frequent insertions and deletions. The B-tree, a tree characterized generally as a balanced search tree with a large branching factor, is especially good in this situation (see the related topics at the end of the chapter). Typically the branching factor of a B-tree is optimized so that disk I/O is minimized when accessing records in the database.
Expression processing (illustrated in this chapter)
A task performed frequently by compilers and hand-held calculators. One intuitive way to process arithmetic expressions is with an expression tree, a binary tree containing a hierarchical arrangement of an expression's operators and operands.
Artificial intelligence
A discipline that addresses many problems traditionally difficult for computers, such as logic-based games like chess. Many AI problems are solved using decision trees . A decision tree consists of nodes that represent states in a problem. Each node is a point at which a decision must be made to continue. Each branch represents a conclusion derived from a series of decisions. Using various rules of logic, branches that cannot possibly contain desired conclusions are pruned, thus decreasing the time to a solution.
Event schedulers
Applications for scheduling and triggering real-time events. Often real-time systems require looking up and retrieving the latest information associated with events as they are triggered. A binary search tree can help make looking up information efficient.
Priority queues
Data structures that use a binary tree to keep track of which element in a set has the next highest priority (see Chapter 10). Priority queues offer a better solution than having to keep a set completely sorted.
Description of Binary Trees
A binary tree is a hierarchical arrangement of nodes , each having up to two nodes immediately below it. The nodes immediately below a node are called its children . The node above each child is called its parent . Nodes can also have siblings , descendants , and ancestors . As you might expect, the siblings of a node are the other children of its parent. The descendants of a node are all of the nodes branching out below it. The ancestors of a node are all the nodes along the path between it and the root. The performance associated with a tree often