CPSC 2120 - DAY 7
MAY 20, 2016

================================================================================

LOOK AT TEST 1 FROM LAST YEAR

Queue
	-Enqueue
	-Dequeue
	-Top
	-isEmpty

*** Possible Test question ***

8 element circular queue, front = 0, rear = 0

5 6 9 D 2 1 8 D 7 6 D

increment rear first, then check to see if front == rear (queue is full)
then you can add items

review doubly linked list

BINARY SEARCH TREES


Left child is less than value of node
Right child is greater than the value of the node

6 9 2 5 4 8 7

	(6)
	/  \
      (2)   (9)
	\    /
	(5) (8)
	/    /
       (4)  (7)


Deleting values from a binary search tree

Items must be comparable
All items have a unique value

Binary Search Trees OPERATIONS!

-Constructor
-Insert
-Find
	-Findmin
	-Findmax
-Remove


Generally Recursive operations

REMOVE OPERATIONS

-NODE IS A LEAF
	REMOVE NODE
-NODE HAS ONE CHILD
	REPLACE NODE WITH CHILD
-NODE HAS CHILDREN
	REPLACE NODE WITH SMALLEST CHILD OF RIGHT SUBTREE

INTERNAL PATH LENGTH

The sum of the depths of all the nodes in a tree
aka add up all the depths

It is a measure of how well balanced a tree is.