16-18 Flashcards
What does a typical red black tree node creation involve?
A typical red black tree node creation involves creating a red node and then checking the parent to see if it is also red. If it is we must fix the double up.
What are the three RBT fixup cases? What is the worst case cost?
x’s uncle is red (parent’s sibling), in this case bush the blackness down one from the grandparent (which must be black if the parent is red). It’s Important to check recursively up the tree when this is done.
X’s uncle is black and x is an inner child (closer to middle). We can solve this by rotating left around x’s parent (if problem is on the left tree).
X’s uncle is black and x is an outer child, we rotate right around x’s grandparent. (if problem is on the left tree.)
Worst case cost of n.
How do we delete a node in a RBT?
To delete a node z, recursively searches for z and then uses replace-the-root. This has two cases:
1. The root has < 2 nonempty children, replace it by a child
2. If the root has two children replace the root with it’s successor (minimum of right subtree).
Once this has been done we must fix up any violations in the RBT.
What are the deletion RBT fix up cases?
Let y be the node that gets spliced, z is the node to be deleted, x is the child that replaced y and w is the new sibling of x.
There are 4 cases:
1. X’s sibling, w is red, fix this and then go to next cases.
2. W is black and has two black children, fix (e.g by making red) then traverse.
3. W is black and w’s inner child is red and outer child is black, fix(rotate the children) then go to case 4.
4. W is black and w’s outer child is red, fix(rotation around the parent) and terminate.
The trick to fixing all of these is to give x and extra black value (giving it 2* black value), we move this extra black value up the tree until we can give it to a red node or we reach the root.
What is the worst case complexity for RBT deletion?
log n
Why do we need B-trees?
Different storage systems e.g ram/HDD/SSD have different minimum addressable units. Therefore it makes sense to have data structures that use the minimum addressable unit as their base node size.
What is a B tree? What properties does it satisfy?
A B tree is an extension of a BST, instead of up to 2 children a B-tree can have up to m children for some pre-specified integer m. M is typically chosen so that a B-tree node will take up one page on the drive.
A B-tree of minimum degree t satisfies the following properties:
1. Every node has at least t-1 and 2t-1 keys except for the root.
2. Every non-left node(except root) has at least t and at most 2t children
3. 3. The root has at least two children if it is now a leaf node
4. A non-leaf node with k-children contains k-1 keys.
5. All leaves are at the same height.
How do we insert in a B Tree
Inserting in a B tree involves finding an appropriate leaf where it should go, we may have to split the leaf if it is already full(has too many keys).
What are the B tree deletion cases?
There are three cases for deleting from a B-tree:
X is a leaf and contains the key, just delete the key from this node.
X is an internal node and contains the key: three subcases
1. Predecessor child node has at least t keys (replace it with the inorder predecessor and recursively delete the new predecessor).
2. Successor child node has at least t keys (replace with inorder successor and recursively delete the new successor).
3. Neither predecessor nor successor child has t keys.(Merge the two children and push the key down into the new child, then recursively delete the key).
X is an internal node but doesn’t contain the key, find the child subtree of x that contains the key if it exists. There are three subcases
1.child has at least t keys. Recurse to c.
2. c has t-1 keys and one of its siblings has t keys.
3. c and both its siblings have less than t keys.
What does a graph consist of and what is an adjacency matrix?
A graph, G, consists of a set of vertices, V, and a set of edges, E. Vertices are specified by unique labels and an edge is an ordered pair of vertex labels. A graph may be directed or undirected.
An adjacency matrix is an n*n Boolean array such that a value will be 1 if the vertex shares an edge with the other vertex and 0 otherwise.
What is an adjacency list and why is this better than a matrix?
An adjacency list is much more space efficient, every position in the array is a linked list containing all the vertices that the vertex in that position has an edge with. The graph is better for computational power but wore for space.
What are the most common operations on a graph and which is the adjacency matrix and list better for?
The three most common operations on a graph besides insertion and deletion are: given two vertices j and k, is there an edge between them?
given vertex j, find all adjacent vertices.
Given vertex j as a starting point, traverse the graph.
The first of these is supported best by the adjaceny matrix, while the second and third are best supported by adjacency lists.
How do we do a breadth first search?
To do a breadth first search for every vertex u we compute the distance from the source vertex s to u and store it in a variable d[u]. Initially the value of the variable d[u] is set to a default. If we do this to a binary tree this gives us a level order traversal.
