CSCI 211 Test 2 Flashcards
a tree is a
non-linear structure in which elements are organized into a hierarchy; it is comprised of a set of nodes in which elements are stores and edges connect one node to another, and each node is located on a particular level
a node can have ? parent(s)
only one
a node with no children
leaf node
not the root node or a leaf node
internal node
a subtree is
a tree structure that makes up part of a larger tree
one important criterion for classifying trees is
the number of children it can have
defining trees (3 things)
- Nodes connected by edges
- Can be classified by max # children
- Do not have cycles or “loops” - they are recursive structures
binary tree
tree in which nodes have at most two children
a tree is balanced if
all of the leaves of the tree are on the same level or 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 tree is complete if
it is full, or full to the next-to-last level with all leaves af the bottom level on the left side of the tree
all tree traversals start at the ? of the tree
root
each node can be thought of as the ? of a subtree
root
list the four classic types of tree traversals
- Preorder
- Inorder
- Postorder
- Level-order
Preorder
Visit the root, then traverse the subtrees left to right
Inorder
Traverse the left subtree, then visit the root, then traverse the right subtree
Postorder
Traverse the subtrees from left to right, then visit the root
Level-order
Visit each node at each level of the tree from top to bottom and left to right
expression tree
a tree that shows the relationships among operators and operands in an expression; evaluated from the bottom up
decision tree
a tree whose nodes represent decision points, and whose children represent the options available
binary search trees
elements are organized to facilitate finding a particular element when needed - the left subtree of each node n contains elements less than the element stored in n and the right subtree of each node n contains elements greater than or equal to the element stored in n
a LinkedList is more efficient than a BST for which operations?
removeFirst and first
a right rotation on a BST
- make the left child element of the root the new root element
- make the former root element the right child element of the new root
- make the right child of what was the left child of the former root the new left child of the former root
a left rotation on a BST
- make the right child element of the root the new root element
- make the former root element the left child element of the new root
- make the left child of what was the right child of the former root the new right child of the former root
an AVL tree
ensures a BST stays balanced because for each node in the tree, there is a numeric balance factor (the diff between the heights of its subtrees)
heap (technically a minheap)
a complete binary tree in which each element is less than or equal to both of its children
is a heap a binary tree? a binary search tree?
yes; no
adding a new element to a heap
- add as leaf
- move element upward toward root, exchanging positions with its parent, until the relationship among the elements is appropriate
removing the min element of a heap
- move the last leaf of the tree to be the new root of the tree
- move it down the tree as needed until the relationships among the elements is appropriate
priority queue
removes elements in priority order, independent of the order in which they were added; a heap is a classic mechanism for implementing
we would rather implement heaps with ? than ?
arrays than links
implementing heaps with arrays: a parent element at index n will have children stored at ? and ? of the array; conversely, for any node other than the root, the parent of the node is found at index ?
2n+1 and 2n+2; (n-1)/2
heap sort
sorts a set of elements by adding each one to a heap, then removing them one at a time
set
a collection with no duplicates; primary purpose is to determine whether an element is a member
map
a collection that establishes a relationship between keys and values; the goal is to have an efficient way to obtain a value given its key
keys of a map must be ?, but multiple keys could map to the same object
unique
implementation of sets and maps using trees
all of the basic operations are performed with O(logn) efficiency
an element in a hash table is stored in a location based on a ?
hash function
a hash function makes some calculation based on the ?
element
multiple elements may be stored in the same location of a hash table
“collision”
a hash function that maps each element to a unique location is called a ?
perfect hashing function
hash code
a short sequence of bits computed from the contents of a longer piece of data (desirable for diff data to produce diff hash codes)
hash function
maps a data value (or its hash code) to an array index (use to decrease the number of possible indexes)
each location in a hash table is called a
“cell” or “bucket”
access time to a particular element in a hash table is ? of the number of elements stored
independent
