Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
10 Cards in this Set
- Front
- Back
|
find query
|
check if two objects are in the same set
|
|
|
union command
|
replace sets containing two objects with their union
|
|
|
what data structures are used for implementing weighted quick-union with path compression (WQUPC)?
|
an id array whose index is a node id and the value is the parent node. a size array whose index is a node's id and the value is the size of the tree the node belongs to
|
|
|
what is the idea behind quick-union?
|
keep track of items that are connected using a tree structure. union is fast because we can join two sets by making the root of one tree the child of the root for the other tree.
|
|
|
how does weighted quick-union work?
|
keep track of the sizes of each tree and always add the smaller tree to the bigger tree, this keeps the height of the trees smaller so find operations are faster
|
|
|
why does performing a weighted quick-union ensure for any object the depth of its tree is at most lg n
|
every time a union is performed the depth of the object's tree increases by at most 1. the size of the tree for the object at least doubles. a tree can only double at most lg n times.
|
|
|
how does path compression work in with union-find?
|
the root of a node is calculated by visiting the ancestors until the root is reached. path compression sets the parent of each ancestor to the root. this makes the trees flat, which means performing union and find operations are faster.
|
|
|
what is the complexity of performing any sequence of m union and find operations on n objects using weight union-find with path compression?
|
O(n + m lg* n) (the first n is for the make-set operations and the m lg* n is for each union and find operation)
|
|
|
what is lg* n?
|
the number of times lg can be applied until 1 is reached
|
|
|
what are some example applications of union-find?
|
networks connectivity, kruskal's minimum spanning tree algorithm, hinley-milner type inference, equivalence of finite-state automata
|
