CSE 332: Data Abstractions
Autumn 2014
Terminology
This is a list of terms that might help you study for exams. It
does not include all the terms that you will have learned in
prerequisite courses.
- abstract data type
- worst case running time
- asymptotic running time
- big O
- big Omega
- big Theta
- rule of sums
- rule of products
- dictionary
- binary search tree
- AVL tree
- AVL balance
- height and depth of a tree node
- single and double AVL rotations
- splay tree
- splay
- concatenation of splay trees
- zig-zag and zig-zig rotations
- amortized running time
- hashing
- hash function
- hash table
- collision
- collision resolution
- separate chaining
- open addressing
- linear probing
- double hashing
- load factor
- rehashing
- universal class of hash functions
- quicksort
- pivot
- mergesort
- recurrence
- undirected graph
- directed graph
- vertex
- edge
- adjacent
- neighbor
- adjacency matrix
- adjacency list
- path
- cycle
- connected graph
- acyclic
- topological sort
- breadth-first search