Term
Binary Trees types
Full
Complete
Perfect |
|
Definition
Full- all nodes have either 2 or 0 children
Complete - All rows are filled except for the bottom row which all nodes are pushed to the left
Perfect - Every level is full including last.(2^(n) -1 = nodes, n= height); |
|
|
Term
| Recursive binary tree search (algorithm) |
|
Definition
| If (tree is empty) return null: else if( target matches root node data) return root.data else if (target is less that root node) return(result of searching left subtree) else return(result of searching right subtree) |
|
|
Term
|
Definition
if tree is empty
return
else
visit root
preorder left subtree
preorder right subtree |
|
|
Term
|
Definition
if tree is empty
return
else
Inorder left subtree
visit root
inorder right subtree |
|
|
Term
| Postorder function algorithm |
|
Definition
| if tree is empty return else postorder left subtree postorder right subtree visit root |
|
|
Term
| Data members for binary tree node |
|
Definition
|
|
Term
| recursive Binary Search tree algorithm |
|
Definition
if (root is null)
return null
compare target value with root value
if equal return root value
else if target is less than root return left subtree search else return right subtree search |
|
|
Term
| Big O of searching Binarytree |
|
Definition
|
|
Term
| Binary Tree isleaf method |
|
Definition
public boolean isLeaf(){
return (root.left==null&& root.right==null); |
|
|
Term
|
Definition
| a complete binary tree where the root value is the smallest item in the list every subtree is a heap |
|
|
Term
| Inserting into heap (Algorithm)(book,333) |
|
Definition
| -Insert the new item in the next position at the bottom of the heap -while new item is not at the root and new item is smaller than its parent -swap new item with its parent, moving the new item up in the heap. |
|
|
Term
| removing item from a heap( book,334) |
|
Definition
remove the item in the root node by replacing it with the last item in the heap.
while(the last item in the heap has children, and the last item is larger that either of its children.
-swap the last item with its smaller child, moving it down in the heap. |
|
|
Term
| Formula for finding a nodes children |
|
Definition
Left child - 2*position+1
Right Child - 2* position+2 |
|
|
Term
| formula for finding a nodes parent |
|
Definition
|
|
Term
| Breadth first traversal of binary Tree(book,357) |
|
Definition
put root into queue
while{ queue is not empty
v=get from queue
print v;
if (v.left!=null)
putv.left in queue
if v.right!=null)
putv.right into queue |
|
|
Term
| Hash table retrieval complexity |
|
Definition
|
|
Term
|
Definition
| A program that acts as a virtual machine. |
|
|
Term
| 6 steps of creating a GUI in the right order: |
|
Definition
import packages
set up top level containers
apply layout
Add components
register listeners
show it to the world |
|
|
Term
| make a component c visible on the screen |
|
Definition
| add to a visible contatiner |
|
|
Term
| Data members for a Single linked List |
|
Definition
private Node head;
private int size; |
|
|
Term
| Data members for Single Linked List node class |
|
Definition
private Node next;
private E value; |
|
|
Term
| Single Linked list add first method |
|
Definition
public void addFirst(E e) {
Node temp = new node;
temp.next=head.next;
head.next=temp;
size++; } |
|
|
Term
| Single linked list iterator next method |
|
Definition
public E next() {
if (cursor == null)
throw new NullPointerException(" next from iterator ");
Node n = cursor;
cursor = cursor.next;
return n.value;
} |
|
|
Term
| what does a single linked list class implement |
|
Definition
|
|
Term
| Insert item at front of Single linked list complexity: Steps: |
|
Definition
| O(1) Create temp node set temp node.next to head.next set head.next to temp. |
|
|
Term
| Double Linked list data members |
|
Definition
private E Data
Private Node next
Private Node previous |
|
|
Term
| steps for inserting into a double linked list |
|
Definition
Create temp node;
set temp node.next to current;
set temp.previous= current.previous;
set current.previous.next= temp;
set current.prev=temp; |
|
|
Term
| complexity of adding to a double linked list at either end? in the middle? |
|
Definition
|
|
Term
| How to create a circular double linked list |
|
Definition
| set the tail.next to head and head.previous= tail. |
|
|
Term
| methods of stack interface |
|
Definition
Boolean Empty()
E peek()
E pop()
E push(E obj) |
|
|
Term
| complexity of heap get and put |
|
Definition
|
|
Term
Best / avg/worst complexity of :
selection sort
Bubble sort
Insertion sort
Shell sort
merge sort
heapsort
quicksort |
|
Definition
sort best avg worst
selection n^2 n^2 n^2
bubble n n^2 n^2
insertion n n^2 n^2
shell n^7/6 n^5/4 n^2
merge nlogn nlogn nlogn
heap nlogn nlogn nlogn
quicksort nlogn nlogn n^2 |
|
|
Term
| properties of a good hash function |
|
Definition
Uniform distrobution | Minimal Collisions |
(the number 31 is a prime number that generates few collisons) |
|
|
Term
|
Definition
where multiple keys point to the same index
h(k1)=h(k2) and h(k1)!=H(k2) |
|
|
Term
| conflict resolution techniques |
|
Definition
linear probing-incrementing a returned index from a key until item is found or null. ( when items are remove extra measures need to be taken for ensure continuity)
chaining-each key points to a list of items, which removes the problem of continuity |
|
|
Term
| define load factor for hash tables |
|
Definition
| number of filled cells divided by table size(lower loadfactor =better performance); |
|
|
Term
| methods for a comparator interface |
|
Definition
public static int compare(obj 1,obj 2){
boolean equals(obj); |
|
|
Term
Implement
public static int leaves(binaryTree<Integer>Root)
-returns the sum of all the integers of the leaves |
|
Definition
if(root== null)
return;
if(root.left==null&& root.right==null)
return root.value;
return leaves(root.left)+leaves(root.right); |
|
|
Term
|
Definition
URL url = new URL("link");
scanner in = new scanner(url.openstream();
while(in.hasNex()){
String token = in.next()
system.out.print( token); |
|
|
Term
| findmax func for binarytree<integer> |
|
Definition
(if using generic type use Compare)
public static <E extends Comparable<E>> <integer> findMax(BinaryTree<E> root) {
int max=root.data;
if(root.left!=null)
int left = findmax(left.data);
if max<left
max=left
if root.right!=null)
int right = findmax(root.right)
if max<right
max=right;
|
|
|
Term
| complexity of push and pop for a stack |
|
Definition
|
|
Term
|
Definition
| tree of elments based on the frequency of the element.most frequent element is at the top least are at the bottom. used for encodeing and compression. |
|
|
Term
| adding to a binary search tree |
|
Definition
if(root is null)
replace empty tree with new tree with the item as root
return true;
else if(root.data == entry)
return false;//already enterend
elseif(entry<root.data)
recursivly add to root.left
else if (entry>root.right)
recursivly add to root.right
|
|
|
Term
| algorithm for finding the heightof a tree |
|
Definition
if(tree is empty)
height is=0;
if(tree is not empty)
height is the max depth of the nodes. |
|
|
Term
| binarytree depth first search |
|
Definition
put root in stack
while{stack!=empty
r=pop;
print r;
if (r.right!=null)
push r.right onto stack
if(r.left!=null
push r.right onto stack |
|
|
Term
| big o formula in terms of t(n) |
|
Definition
|
|
Term
| selection algo/ complexity |
|
Definition
O(n^2)
–An algorithm which orders items by repeatedly looking through remaining items to find the least one and moving it to a final location |
|
|
Term
| bubble sort algo. complexity |
|
Definition
–Sort by comparing each adjacent pair of items in a list in turn, swapping the items if necessary, and repeating the pass through the list until no swaps are done
O(n^2) |
|
|
Term
| INsertion sort process/complexity |
|
Definition
–Sort by repeatedly taking the next item and inserting it into the final data structure in its proper order with respect to items already inserted.
O n^2
|
|
|
Term
|
Definition
O(nlogn)
–An algorithm which splits the items to be sorted into two groups, recursively sorts each group, and merges them into a final, sorted sequence |
|
|
Term
|
Definition
An in-place sort algorithm that uses the divide and conquer paradigm. It picks an element from the array (the pivot), partitions the remaining elements into those greater than and less than this pivot, and recursively sorts the partitions
best -even split of entries
worst situation is if it is presorted since the left of the pivitot has 0 spaces and right has n+1 space
O(nlogn)
|
|
|
