Algorithms - Trees PDF

Preview

Summary

Algorithms - Trees...

Description

Algorithms - Trees Trees are an ADT that can be implemented using arrays or pointers, of which pointers are by far the most common. Trees can be used to implement other ADT's, such as collections (sets). Structure

Nodes carry data and are connected by branches. In some schemes only leaf nodes or only interior nodes (including the root) carry data. Each node has a branching degree and a height (aka depth) from the root. Operations on a tree include:

   

Get data at root n Get subtree t from root n Insert new branch b and leaf l at root n. Get parent node (apart from when at root) - this is not always implemented.

These operations can be combined to get any data, or insert a new branch and leaf. Binary Trees A binary tree is a tree with nodes of degree at most two, and no data in the leaves. The subtrees are called the left and right subtrees (rather than 'subtree 0' and 'subtree 1'). An ordered binary tree is one which is either an empty leaf, or stores a datum at the root and:

 all the data in the left subtree are smaller than the datum at the root,

 all the data in the right tree are larger than the datum at the root, and  any subtree is itself an ordered binary tree. Usual implementations use pointers to model branches, and records to model nodes. Null pointers can be used to represent nodes with no data. As mentioned earlier, array implementations can be used, but they are normally messy. An ordered dictionary can be used to implement a binary tree. Such a tree would be structured like this:

 These trees combine advantages of an ordered array and a list.  The complexity to traverse a complete tree is log2 n, however this is only if the tree is perfectly balanced.

 A completely unbalanced tree will have the properties of an ordered list and will therefore by linear.

When we are considering trees, we should now consider three data invariants:

 order  binary  balance There are two common balance conditions: Adelson-Velsky & Landis (AVL) trees, which allow sibling subtrees to differ in height by at most 1 and red/black trees, which allow paths for nodes to differ a little (branches are either red or black - black branches count 1, red branches count 0 and at most 50% can be red). AVL Trees In AVL trees, searching and inserts are the same as before, but in the case of inserts, if a tree is unbalanced afterwards, then the tree must be rebalanced. Rebalancing The slope is height(left) - height(right). For the tree to be balanced, slope ∈ {-1, 0, 1} for all nodes. If the tree is not balanced, it needs rebalancing using 'rotation'. To rotate, you should set up a temporary pointer for each node and then re-assemble the tree by changing connecting pointers. Deletion from a binary tree There are different methods of deleting from binary trees. One is using ghosts. A cell could have a "dead" marker indicated (however, it must still have the contents for ordering purposes), but this is only useful if deletion does not happen often, otherwise the tree will end up very large with lots of dead cells.

 Insert could also be altered to use these dead cells (if they fit in with the orderings)  Another method that is used is propogation. Here, deletions are pushed down to a leaf, and pushed up cells must be

checked to ensure they are still ordered. The tree may need rebalancing after this happens.

 Lists will always be quicker than trees for deletion.  What about ternary trees? These would give us log3 n, which is < log2 n (where n > 1). In a binary tree: Θ(log2 n), but in a ternary tree, Θ(log3 n). However, log2 n = Θ(log3 n). The base is a constant, so can be disregarded for Θ purposes.  However, ternary trees require harder tests for ordering, so any benefit from having fewer arcs are cancelled out. Tree rebalancing is much trickier, as rotation can not be used. In a case where pointers are very slow (such as on a disk), then ternary trees may be better....