The Tree data structure stores hierarchies, and takes a shape akin to an upside-down "Family Tree." Trees all start with a single root Node. Nodes can have child Nodes. Nodes at the bottom, with no children, are known as leaf Nodes.
Really, Trees are Graphs with more restrictions.
Trees can also serve as the underlying data structure of a List. Like Lists, but unlike Maps, Trees can be ordered collections. Ordered trees allow for more efficient search than a List, but are less efficient than a Map at simple lookups.
The Wikipedia entry on Trees includes more vocabulary along with definitions.
Certain problems are naturally modeled as a Tree. Organization hierarchies, and many kinds of parsed text (code, HTML, JSON). For example, the following equation...
1 + (3 * 4)
... can be recognized as a tree of operators and numerals:
|----+---|
1 --*--
| |
3 4
Trees can also be useful when an ordered List is desired, and you need searching to be better than O(n).
Implement and test Tree and Node classes. Rely on any of the Data Structures you have implemented thus far, along with basic Ruby objects that you create yourself.
Node::new(value): Instantiate a new Node containingvalueNode#add_child(child): Addchildas a child of this nodeNode#value: Return the value of this nodeNode#children: Return a collection of child nodes
Tree::new(node): Instantiate a new Tree withnodeas the rootTree#search {|value| }: Search through the tree.#searchtakes a block that receives the value of the node. It should return the first node for which the block returnstrue, or nil if no node is found.
Have at least one test that constructs a tree that looks like this and verify that you can search and find #baz-box.
----------<body id='foo'>----------
| |
<h1 id='bang'> <div id='bar-box'>
|
<div id='baz-box'>
Implement and test a TreeList data structure. A TreeList is a just a List implementation that uses an ordered Tree behind the scenes. Consider using your Tree as a binary tree in your implementation.
Since this TreeList will be ordered, your methods should only accept elements that implement the comparison operator, #<=>. String, Fixnum and others already implement it, or you can create a simple class.
As you add items to TreeList it should correctly maintain order. If you iterate through the elements later, no matter the order they were added in, they should come out ordered.
Your TreeList class should conform to the following interface:
TreeList#new(): Instantiate a new TreeListTreeList#add(element): Add an element to the listTreeList#index_of(element): Return the index ofelementin the listTreeList#size: Return the size of the listTreeList#each {|element|}: Iterate through the list. The list should be in order.#addshould be faster than O(n). Remember that this is an ordered tree — how can you use this to your advantage? Could#addbe O(n) in a sorted linked list?
Create a #contains?(element) method that is O(log n)