Exam Review 2

Review Exam #2

I. LIFO Stacks
	LIFO - Last In First Out
		Ex: Stack of books
	1)Stack
		a)Applications: infix to postfix
		b)Data Members
			1) A place to hold a collection of like items
				-array
				-linked list
			2) A place to hold the position stack top
			3) Max Size of the stack
		c)methods
			Handout
		d)growth rate

II. FIFO Queues
	FIFO - First In First Out
		Ex: Jack in the Box drive-thru
	1)Queue
		a)Applications: Binary Tree???
		b)data members
		c)methods
		d)growth rate

III. Binary Tree
	1) Definition
		A tree is a recursive collection of nodes where a special node is called the root (r) and can have maximum of two children subtrees T0, T1 each of whose roots are connected by a directed edge to r
	2) Terms
		Node - a point in a tree structure where data is stored
		Directed edges - a connection between two nodes in a tree; also called a branch
		Root - a special node with at least one child; a node with no parent
		Leaf - a node without children
		Parent - r is said to be the parent of each subtree
		Child - a root of each subtree is said to be a child of r; left child and right child
		Ancestor - if a path exist from n1 to n2 then n1 is an ancestor of n2
		Descendant - if a path exst from n1 to n2 then n2 is a descendant of n1
		Level - is the distance of a node from the root; root is at level zero
		Height of a tree - is equal to the height of the maximum level
	3)Traversals
		a)inorder
			Left Root Right
		b)preorder
			Root Left Right
		c)postorder
			Left Right Root

IV. Binary Search Tree (BST)
	1) Definition
		A binary search tree is a binary tree
			Where the value of the left child is less than the value of the parent
			And the value of the right child is greater than the value of the parent
	2)Growth Rate for BST
		Worst case growth rate: O(n)
		Average case growth rate: O(logn)
	3)Growth Rate for operations
		O(logn)
	4)Operations for BST
		a)Insert
		function: insert(newItem)
			Pseudocode:
				create new node, insert data, and set both child pointers to NULL
				search the tree to find the location to inser the new item; insert at the end
				insert new node as leaf
				insert new node into the proper location
			growth rate: O(logn)
		b)Delete
		function: delete(deleteItem)
			Pseudocode:
				Find the node
				Delete the node
					1. Delete into an empty tree (only a root)
					2. Delete a leaf node
					3. Delete node with one child
					4. Delete node with 2 children
			1. Delete into empty tree
				Pseudocode:
					Delete into an empty tree;
					assign temp to root;
					delete temp;
					NULL root;
				growth rate: O(1)
			2. Delete a leaf node
				Pseudocode:
					Determine if a leaf node;
					Delete current;
					Set previous child pointer to NULL;
			3. Delete node with one child
				Pseudocode:
					Determine if there is only one child
					Set previous child pointer to point to grandchild
					Delete current node
			4. Delete node with 2 children
				Pseudocode:
					Determine if there are 2 children
					Find replacement value(delete item value)
					Delete original, replacement node; this will be a lear or a one child node
				growth rate: O(logn)
		c)Search
		Non-recursive function: search()
		PseudoCode:
			if IsEmpty
				return error
			else
				search tree
		code:
			set found=false;
			set current=root;
			while(current!=NULL && current==found)
				if(current -> info==search info)
					set found=true;
				else
					if(search info<current -> info)
						set current= currenr->left;
					else
						set current=current->right;
		Growth rate: O(logn)

V. Recursion
	1)What is Recursion?
		Recursion is a unique problem-solving approach where you solve a problem by repeatedly breaking the problem into smaller versions of the same problem, until you reduce the subproblem to a tribial size that can be easily solved
		Once the trivial solution is found, keep repeatedly combinin the solution until the original solution is found to the original problem
	2)A recursive function must solve
			A base case (simplest solution)
			General case (diminished part of the proglem making progress toward the base case)
	3)Growth rate: O(n)
	4)
	5)