Tree Algorithms

wb_incandescentOverview

This module explores the exciting world of binary trees and their related algorithms for building, modifying, walking, searching, and sorting.

list Tree Reference

The following pages are extractions from "Introduction to Algorithms" by Cormen, Leisserson, Rivest, and Stein; MIT Press;(c)2009. These reprints are made under Educational Fair Use terms for non-commercial reuse in an educational context.

Cover of source text

list Exercise 1: Binary tree walks

Build the tree steps:

1. Choose a topic/category of people, things, or events about which you can construct nodes keyed by a string and whose value is data of any kind. This example creates nodes representing nuclear power facilities in the US whose keys are the plant name and values are the megawatts of electrical energy generated. Explore the wikipedia entry.
2. On cards or scraps of paper, generate about a dozen nodes: print the key on the front, and the value on the back.
3. Shuffle your cards thoroughly
4. Build a binary tree using the shuffled deck of nodes: place the first node as the root of your binary search tree. Then place the next card on the stack: if it comes before the root, place as the root's left child node; if it follows the root node in sort order, place it as the right child.
5. Continue placing nodes and assembling your binary tree

Traverse the tree steps:

1. Review the in-order tree traversal algorithm on the resources tab of this module.
2. Diagram your recursive method calls on one sheet of paper, and record your theoretical program output on another sheet: simulate calling the in-order-traversal(root r) on your root node and carefully move through the tree, tracking each nested method call on the stack.
3. Prove that an in-order traversal of a correctly built binary search tree produces output in correct sort order!

Submission

Generate images of all your work. Visit our cloud drive root >> mod-trees >> {create a folder with your public name and node topic}

Upload your images and rename them to sensible things.

cloud_upload

Root of DS cloud MS OneDrive

Screen shots of in-class tree-building exercise

list Building a tree in C++

Video of class session with instructor demo of traversal algorithm encoding

list Groups! Insert & Delete TreeNodes

Objective

Devise using pseudocode algorithms for inserting nodes in a binary search tree and deleting nodes in a binary search tree.

Translate the pseudocode into C++ code and squash bugs

Google doc group workspace

Open the tree algorithms google doc and navigate to your group's section using the table of contents.

Group-work procedure

1. Navigate in the google doc to your group number's section
2. Introduce yourselves and share a personal connection to trees
3. Start with the insertion algorithm: choose a recorder and a facilitator, the other members are "thinkers" for this algorithm
4. Proceed through the sub-sections for insertion: declare the algorithms goals and outputs; write the pseudo-code; compile a storage requirement list; hack out the C++
5. Change roles for the deletion algorithm and work through the sub-sections.

list BST project specs

objective	Model a tree-based data structure in C++ and interact with that tree in various ways
required organs	Manually built tree In-order traversal
insert/delete	Insert Write a function which, given a tree's root and a node to insert, locates the correct spot in the tree for the given node, and wires it up appropriately to parent/child Delete Write a function that given a tree's root and a node to delete, locates that node and removes it from the tree, correcting any linking necessary to preserve the remaining branches.
optional: display tree structure	Choose an appropriate walk algorithm that will allow you to easily display the nodes of a given tree onto the console as a vertically oriented diagram of connected nodes. Use clever characters to to the drawing of the linking lines.
optional: array encoding	As a challenge exercise, write a function that can encode your tree in one or more two-dimensional arrays instead of node objects. Write a function to decode the arrays back into TreeNode objects.
documentation	Include comments above each method describing its key functionality. Include comments above or a the end of each unclear/important line of code. You should write all the code for your program, copying nothing from any other resource. If you use somebody else's code closely--i.e. using its essential structure but changing variable names--include a citation in your comments.
work products	For all project outcomes, please satisfy these criteria in preparation for building a professional work portfolio. Comment your code, making note of sections of code contributed by group members or outside resources in a 1:1 kind of way. Run your program and capture 1 or more screen shots of it doing its thing Diagram your tree as created in your code; Include an image or PDF of this in your project deliverables. A written overview of your program written in markdown and included in a file called readme.md Your project is either pushed or uploaded directly to a github account You've tested to ensure that the readme shows up grid_on Master repl and work tracking spreadsheet