Monthly Archives: January 2018

BSTs – Proposition

Screen Shot 2015-02-27 at 7.44.59 AM

2-3 search trees
Screen Shot 2015-02-27 at 7.46.26 AM

We introduce in this section a type of binary search tree where costs are guaranteed to be logarithmic. Our trees have near-perfect balance, where the height is guaranteed to be no larger than 2 lg N.

Proposition.

Search and insert operations in a 2-3 tree with N keys are guaranteed to visit at most lg N nodes.

Typical 2-3 tree built from random keys
However, we are only part of the way to an implementation. Although it would be possible to write code that performs transformations on distinct data types representing 2- and 3-nodes, most of the tasks that we have described are inconvenient to implement in this direct representation.

Implementing Binary Search Trees

Binary Trees

Homework:
Implementing Binary Search Trees: With Links

1. How are the constructors implemented?
2. Write the pseudocode for public void addElement (T element). Draw an example of adding an element to a BST.
3. Write the pseudocode for public T removeElement (T targetElement). Draw an example of removing an element to a BST.
4. Write the pseudocode for public void removeAllOccurrences (T targetElement).

LispList interface

November 13th, 2014
Screen Shot 2014-11-13 at 7.29.51 AM
Linked lists. A linked list is a recursive data structure that is either empty (null) or a reference to a node having a generic item and a reference to a linked list. To implement a linked list, we start with a nested class that defines the node abstraction

private class Node {
   Item item;
   Node next;
}

Homework:
LispList interface and the EmptyList and NonEmptyList classes implementations.
Write a test program that constructs a list and prints it.
From Wikipedia:
Lisp (historically, LISP) is a family of computer programming languages with a long history and a distinctive, fully parenthesized Polish prefix notation. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older (by one year).
The name LISP derives from “LISt Processing”. Linked lists are one of Lisp language’s major data structures, and Lisp source code is itself made up of lists. As a result, Lisp programs can manipulate source code as a data structure, giving rise to the macro systems that allow programmers to create new syntax or new domain-specific languages embedded in Lisp.

Bag Class

Classwork:
Go to Classroom Salon to discuss the Bag Class and watch only the visual representation of stacks and queues video.

Screen Shot 2014-09-23 at 8.24.26 AM

Homework: Use the API discussed in class to develop your own implementation of the Bag Class. Make sure you use generics.

Trees

September 24th, 2015

Classwork: Work on assignments.
Homework: Read 9.1 Trees and 9.2 Strategies for Implementing Trees

Not this kind of trees:
trees

or this kind!
example_flowchart_vacationDecisionTree

More like this kind:
maxrestree
BTW This picture is worth a 1,000 words!

It comes from this video I found.

Binary Trees 2015

September 29th, 2015

Binary Trees

Videos from mycodeschool.com

Binary Tree: Level Order Traversal

Binary Tree Traversal: Preorder, Inorder, Postorder

Delete a node from Binary Search Tree

Inorder Successor in a binary search tree

Check if a binary tree is binary search tree or not

Homework:

1. Draw the binary search tree that results from adding the following integers (34 45 3 87 65 32 1 12 17).

2. Look into the BinarySearchTreeADT in the book.

3. Read Implementing Binary Search Trees: With Links

Trees Assignments

September 25th, 2015

Trees

  • A tree is a nonlinear structure in which elements are organized
    into a hierarchy.
  • A tree is composed of a set of nodes in which elements are stored and edges that connect one node to another.
  • Each node is at a particular level in the tree hierarchy.
  • The root of the tree is the only node at the top level of the tree.
  • There is only one root node in a tree.
  • The nodes at lower levels of the tree are the children of nodes at the previous level.
  • A node can have only one parent, but a node may have multiple children.
  • Nodes that have the same parent are called siblings.
  • The root node is the only node in a tree that does not have a parent.
  • A node that does not have any children is called a leaf.
  • The root is the entry point into a tree structure. We can follow a path through the tree from parent to child.
  • We can follow a path through the tree from parent to child.
  • A node is the ancestor of another node if it is above it on the path from the root.
  • The level of a node is also the length of the path from the root to the node.
  • This path length is determined by counting the number of edges that must be followed to get from the root to the node.
  • The height of a tree is the length of the longest path from the root to a leaf.

Tree Terminology Tree path and level

Tree Types

  • A tree that has no limit to the number of children a node may have is called a general tree.
  • A tree that limits each node to no more than n children is referred to as an n-ary tree.
  • A tree in which nodes may have at most two children is called a binary tree.
  • A tree is considered to be balanced if all of the leaves of the tree are on the same level or at least within one level of each other.
  • A balanced n-ary tree with m elements will have a height of log base n of m.
  • A balanced binary tree with n nodes will have a height of log base 2 of n.

Tree balanced

  • A complete tree is related to the balance of a tree.
  • A tree is complete if it is balanced and all of the leaves at the bottom level are on the left side of the tree.
  • Another way to define this concept is that a complete binary tree has 2^k nodes at every level k except the last, where the nodes must be leftmost.
  • An n-ary tree is considered full if all the leaves of the tree are at the same level and every node is either a leaf or has exactly n children.

Complete Trees

(a) and (c)–are complete
Only (c) in Figure full

Homework:
Visit edmodo.com to answer the following questions
1. What is a tree?
2. What is a node?
3. What is the root of the tree?
4. What is a leaf?
5. What is an internal node?
6. Define the height of a tree.
7. Define the level of a node.

Read Tree implementation with arrays.