Trees

Notes

Goodrich Chapter 8 Trees

Definitions

Trees - most important nonlinear data structures in computing

Relationships in trees are hierarchical

Each element in a tree has a parent element and zero or more child elements

Formally, define tree T as a set of nodes storing elements such that the nodes have a parent-child relationship satisfying the following properties:

• If T is non-empty, it has a special node, called the root of T, that has no parent.
• Each node v of T different from the root has a unique parent node w; every node with parent w is a child of w.

Relationships

Node relationships:

• Sibling nodes are nodes that share a parent
• External nodes are nodes with no children - total number is n_E
• Internal nodes are nodes with 1 or more children - total number is n_I
• Node u is an ancestor of node v is u = v or if u is an ancestor of the parent of v.
• The stubtree of T that is rooted at node v is the tree consisting of all descendants of v in T - including v itself.

Edges Paths

Edges and paths:

• An edge of three T is a pair of nodes (u,v) such that u is the parent of v or vice-versa
• A path is a set of consecutive edges - or, a set of consecutive nodes connected by edges.
• A tree is ordered if there is a meaningful linear order among the children of each node.

Example:

• Documents like books are hierarchically organized as a tree whose internal nodes are parts, chapters, sections, and leaves are paragraphs, tables, figures

Ordered/Unordered

Ordered vs unordered

• Ordered tree - the order of the sibling nodes is important
• Unordered tree - there is no precedence with respect to one sibling or the other
• Examples of ordered trees occur when there are ordered operations (e.g., siblings ordered according to order of birth)
• Examples of unordered trees occur with enumerations or functionality (org charts, divisions in a company)

Implementation

Tree abstract data types:

• Things get a bit confusing from here. Goodrich separates the concept of a "Position" from the concept of a "Node."
• The Position is a location in the tree, the Node is a four-pointer container. k

Abstract class:

• Tree is an example of an abstract class implementation
• In Python, each virtual function will raise a NotImplementedError("Must be implemented by subclass")
• In Python, errors in arguments pointing to invalid positions should raise a ValueError
• In Java, we define the functions to be abstract and require that inheriting objects define them. Java/Abstract Classes

The actual implementation will differ depending on the type of data we are storing and the various requirements we might have for it (e.g., a faster algorithm may be rejected due to high memory usage and memory constraints).

There are some concrete methods that can be defined, if they are independent of implementation. Some examples include:

• is_root (parent is null)
• is_leaf (number of children is 0)
• is_empty (T if no nodes in tree)

Computing depth and height:

• Depth of p is the number of ancestors of p, excluding p itself
• Depth is the distance (in other nodes) to the root node
• The height of a node is the maximum height of each of the node's children
• The height of the entire tree is the maximum depth of its leaf positions.

Algorithmic analysis

Analyze the following two methods to obtain the height:

def _height(self):
  return max(self.depth(p) for p in self.positions() if self.is_leaf(p))

This will call depth function on each tree, and the worst-case depth is n.

That means we're doing

$ \sum_{i=1}^{n} j = \dfrac{n(n+1)}{2} \sim n^2 $

Height runs in O(n^2)

An alternative method utilizes recursion:

def _height2(self,p):
  if(self.is_leaf(p)):
    return 0
  else:
    return 1 + max(self._height2(c) for c in self.children(p))
    # for each child, compute height, and return the maximum height + 1

Binary tree

See Binary Tree.