Binary Trees/LinkedBinTree

Linked memory structure binary tree

This page describes a Binary Trees implemented using a linked memory structure.

Notes

An abstraction for implementing a linked binary tree is to think about the positions (or locations in the tree) independently of the nodes (or bundles of links that represent elements). This starts to make more sense when you see either an array-based implementation or an object-oriented abstract interface, but essentially we want to think of each of the potential positions of nodes in a binary tree, and number them one level at a time (1, 2 3, 4 5 6 7, etc.). This way, we have a "shadow tree" and can think about "positions" in that frame of reference.

In Java, this is performed by creating a Position interface that provides a way for abstract data structures to still define useful general functionality, but leave most of the definitions to the concrete implementation. In Python, it is performed by creating an abstract class.

Each node has pointer to left and right children, a pointer to the parent, and a pointer to the element that the node stores.

Here's what the Goodrich book says about nodes versus positions: "We define a simple, nonpublic _Node class to represent a node, and a public Position class that wraps a node. We provide a _validate utility for robustly checking the validity of a given position instance when unwrapping it, and a _make_position utility for wrapping a node as a position to return to a caller.

In Python, position class can also define __eq__ and __neq__ to get p==q or p!=q syntax

Binary Tree Abstract Data Type Interface

See also: Abstract Data Types - section on binary trees

Here is the interface that the binary tree abstract data type requires this object to expose:

• add_root
• add_left
• add_right
• set//replace
• remove//delete
• attach(p,t1,t2)

These can each be implement in O(1) worst case time with a linked representation. Delete and attach are the most complicated, but still only utilize a constant number of operations.

To avoid undesirable update methods being inherited by sub-classes, these methods are provided as nonpublic methods. So, for example, a _delete method is provided in lieu of a delete method.

MutableLinkedBinaryTree class would be one that exposed public versions of each of the six update methods.

Algorithmic Analysis

The efficiency of operations are as follows:

• Single list quantities - length and is_empty - will run in O(1) time
• Accessor methods root, left, right, parent, and num_children will take O(1)
• Sibling and children methods are based on constant number of calls to other ancestors, so run in O(1) time
• Depth method runs in O(d+1) time, where d is depth of given position; height method runs in O(n) time
• add_root, add_left, add_right, replace, delete, attach each run in O(1) time

Traversal:

• pre and post order traversal, in-order traversal
• theoretically will take O(N) time if we store links and O(N log N) time if we don't (worst case: have to traverse the height of the tree log(N))