CMSC 256 Test 3 Comprehensive Study Guide on Sorting Algorithms and Tree Traversal

Root

In a tree, the topmost node of the tree. All other nodes in the tree are descendants

Leaf

In a binary tree, it is any node that has two empty children.

In general tree, any node can be this if it has no children

Parent

In a tree, the node P that directly links to a node A.

Child

In a tree, the set of nodes directly pointed to by a node R

Internal node(or inner node)

In a tree, any node that has at least one non-empty child

Siblings

Any other node with the same parent as a node A

Descendant

All of the nodes that can be reached from a node A by progressing downwards in tree

Subtree

Subset of the nodes of a binary tree that includes some node R of the tree as the root along with all the descendants of R

Height

One more than the depth of the deepest node in the tree

Bubble sort implementation/how it works

-need an array w/values to sort

-Inner for loop moves from left to right comparing adjacent elements

-Highest one placed at rightmost end

-Repeats process until data is sorted

Selection sort implementation/how it works

-finds the largest element in an unsorted list, then next largest, and so on

-goes from left to right through entire unsorted portion of array

-only one swap is required to put element into place

Insertion sort implementation/how it works

Bubble Sort BigO

Best efficiency: O(n)

Average efficiency: O(n^2)

Worst efficiency: O(n^2)

Selection sort BigO

Best efficiency: O(n^2)

Average efficiency: O(n^2)

Worst efficiency: O(n^2)

Insertion sort BigO

Best efficiency: O(n)

Average efficiency: O(n^2)

Worst efficiency: O(n^2)

Worst case for comparisons total in selection sort

n^2/2

When is selection sort a good choice to use for sorting an array?

When the cost of a swap is large, such as when the records are long

Total # of swaps required in selection sort

n-1

T or F

Insertion Sort is a stable sorting algorithm. Recall that a stable sorting algorithm maintains the relative order of records with equal keys.

True

Depth

The length of the path from root of the tree to node M

Preorder traversal

Root, left child, right child

Post-order traversal

Left child, right child, root

Inorder traversal

Left child, root, right child

Level order traversal

Process all nodes of a tree by depth: first the root, then the children of the root, etc.

How would you change the implementation of a binary heap(min heap) to be a max heap?

Change comparisons

General tree

A tree in which any given node can have any number of children. Tend to be harder to implement due to this reason

Binary tree

A tree with a finite set of nodes which is either empty, or else has a root node together of left and right subtree which are disjoint from each other and the root

General tree properties

Single parent: has precisely one parent except for the root which has no parent