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 the array implementation, 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.

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
• replace
• delete
• attach

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