Today I want to discuss a few algorithms from the Algorithms and Data Structures. We will quickly review tree and graph algorithms.
To delete a node from a binary search tree:
we have to consider three cases:
If the current has no right child, then the current's left child becomes the node pointed to by the parent.
If the current's right child has no left child, then the current's right child replaces the current in the tree
If the current's right child has a left child, replace current with the current's right child's left-most node.
To insert a node to a binary search tree, insert as a leaf with the check for the parent.
An AVL is a self balancing binary search tree. AVL trees maintain the property that the height of the left and right subtree must differ by at most 1.
If a node has no sibling, it's height is considered -1 for that subtree.
To insert a node into the AVL tree, insert the node just as in the BST. Then as a next step, if the height is violated, rotate the tree to adjust the height at the node where the violation is detected. Check each node for violation up the parent chain because one rotation may not be sufficient.
If the node with the violation is A, then
If a node is inserted into the left subtree of the left child of A, then there is one rotation
If a node is inserted into the right subtree of the right child of A, then there is another rotation
If a node is inserted into the left subtree of the right child of A, then there is double rotation
If a node is inserted into the right subtree of the left child of A, then there is double rotation.
To delete a node from an AVL tree, is more involved than one rotation because each of the nodes in the parent chain needs to be checked for violations since imbalance may propagate upwards.
An AVL tree comes in useful when subsequent operations access the recently added node such as in the splay trees. Splaying means moving the node to the root by rotations. The tree remains roughly balanced.
A Red-black tree satisfies the additional properties that
Every node is either red or black.
The root and the leaves are black
If a node is red, then its children are black.
For each node, all simple paths from the node to the descendant leaves contain the same number of black nodes.
To insert a node in the red-black tree, insert as in a BST and then fixup the colors with three cases.
case 1 is when we recolor the nodes.
case 2 is when we left rotate the nodes
case 3 is when we right rotate the nodes.
To delete a node in the red-black tree, delete as in a BST and then fixup the colors with four cases
with one more case for the double rotation. Reverse the operations for right and left for the other subtree. In insertion we look up at the parent's sibling and in deletion we look at the sibling of the node and the children of the node for their color.
Graph algorithms are briefly enumerated below.
Breadth first search algorithms traverse reachable vertices with the smallest number of edges. Eg
Dijkstra's single source shortest path algorithm and
Prim's minimum spanning tree
Dijkstra's algorithm extracts the minimum shortest path estimate vertex and adds it to the set of vertices maintained. It then relaxes all the edges outbound from that vertex.
Prim's algorithm builds a minimum spanning tree by adding edges to the tree in a way that is safe and minimum cost for the tree.
Depth first search explores vertex outbound from the most recently added vertex. The nodes are initially white. We color the nodes gray when we discover them and after we have explored the edges, we color them black. The nodes are thus found as in a parenthesis structure and intervals of nodes can either be disjoint, descendant and contained one within the other.
We now look at some data structures.
a hash_map is an associative container that indexes based on the hash of the contained elements as opposed to the map that uses the less than operation on the elements contained. Collisions are resolved to buckets.
A multimap is like a map except that it allows duplicate entries. The range of duplicate entries can be looked up with equal_range. A multiset is a set that allows duplicate keys. Valarrays and bitset are specialized containers.
To delete a node from a binary search tree:
we have to consider three cases:
If the current has no right child, then the current's left child becomes the node pointed to by the parent.
If the current's right child has no left child, then the current's right child replaces the current in the tree
If the current's right child has a left child, replace current with the current's right child's left-most node.
To insert a node to a binary search tree, insert as a leaf with the check for the parent.
An AVL is a self balancing binary search tree. AVL trees maintain the property that the height of the left and right subtree must differ by at most 1.
If a node has no sibling, it's height is considered -1 for that subtree.
To insert a node into the AVL tree, insert the node just as in the BST. Then as a next step, if the height is violated, rotate the tree to adjust the height at the node where the violation is detected. Check each node for violation up the parent chain because one rotation may not be sufficient.
If the node with the violation is A, then
If a node is inserted into the left subtree of the left child of A, then there is one rotation
If a node is inserted into the right subtree of the right child of A, then there is another rotation
If a node is inserted into the left subtree of the right child of A, then there is double rotation
If a node is inserted into the right subtree of the left child of A, then there is double rotation.
To delete a node from an AVL tree, is more involved than one rotation because each of the nodes in the parent chain needs to be checked for violations since imbalance may propagate upwards.
An AVL tree comes in useful when subsequent operations access the recently added node such as in the splay trees. Splaying means moving the node to the root by rotations. The tree remains roughly balanced.
A Red-black tree satisfies the additional properties that
Every node is either red or black.
The root and the leaves are black
If a node is red, then its children are black.
For each node, all simple paths from the node to the descendant leaves contain the same number of black nodes.
To insert a node in the red-black tree, insert as in a BST and then fixup the colors with three cases.
case 1 is when we recolor the nodes.
case 2 is when we left rotate the nodes
case 3 is when we right rotate the nodes.
To delete a node in the red-black tree, delete as in a BST and then fixup the colors with four cases
with one more case for the double rotation. Reverse the operations for right and left for the other subtree. In insertion we look up at the parent's sibling and in deletion we look at the sibling of the node and the children of the node for their color.
Graph algorithms are briefly enumerated below.
Breadth first search algorithms traverse reachable vertices with the smallest number of edges. Eg
Dijkstra's single source shortest path algorithm and
Prim's minimum spanning tree
Dijkstra's algorithm extracts the minimum shortest path estimate vertex and adds it to the set of vertices maintained. It then relaxes all the edges outbound from that vertex.
Prim's algorithm builds a minimum spanning tree by adding edges to the tree in a way that is safe and minimum cost for the tree.
Depth first search explores vertex outbound from the most recently added vertex. The nodes are initially white. We color the nodes gray when we discover them and after we have explored the edges, we color them black. The nodes are thus found as in a parenthesis structure and intervals of nodes can either be disjoint, descendant and contained one within the other.
We now look at some data structures.
a hash_map is an associative container that indexes based on the hash of the contained elements as opposed to the map that uses the less than operation on the elements contained. Collisions are resolved to buckets.
A multimap is like a map except that it allows duplicate entries. The range of duplicate entries can be looked up with equal_range. A multiset is a set that allows duplicate keys. Valarrays and bitset are specialized containers.
No comments:
Post a Comment