Linked Structures
NOTE: Use @SupressWarnings(“unchecked”)
Category Archives: Homework
Stacks – Linked List vs Array
BSTs – Proposition
2-3 search trees
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.
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
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.
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:
or this kind!
More like this kind:
BTW This picture is worth a 1,000 words!
It comes from this video I found.
Queues and Stacks Ex 3, 4 and 7
Classwork:
Stack Class and its applications.
Exercise 3 – discuss it in Classroom Salon
Homework:
Exercises 4 and 7
Implement the Queue Class
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 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.
- 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.
(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.