EduCollection

Euler Tour of a Tree - can also be applied to a general graph. This is a useful technique to apply on trees to linearize them (i.e. convert to a flat list/array) for further processing. The original tree can be reconstructed from the Euler tour, so in some way, it is a tree serialization technique.

Binary min-heap deletion. Heap Sort follows directly from it.

Efficient computation (in linear time) of the Failure Function for the KMP string matching algorithm. Using this computed failure function, one can efficiently search for a pattern (the string for which we computed the failure function) in a block of text.

Computation of the Failure Function for the KMP string matching algorithm. This slide explains the basic idea behind what the failure function stands for and doesn't focus on efficient construction of the same.

General Technique: As soon as a node is visited, we check if both nodes in a query pair that involves the visited node have been visited. If so, we find the root node of the other node's subtree (not the most recently visited node in the pair) and set that as the LCA of the pair of nodes.

RMQ => Range Minimum (or Maximum) Query. Problem Statement: Given an array of numbers, pre-process the array so that questions such as "Return the maximum element between array indices 11 and 23" can be answered efficiently. Described solution: The solution describes pre-processes the input array (of n elements) in O(n^2) time, and answers RM queries in O(1) time.

RMQ => Range Minimum (or Maximum) Query. Problem Statement: Given an array of numbers, pre-process the array so that questions such as "Return the maximum element between array indices 11 and 23" can be answered efficiently. Described solution: The solution described pre-processes the input array (of n elements) in O(n lg n) time, and answers RM queries in O(1) time.

Building a Cartesian Tree. A Cartesian Tree is a heap-like structure such that the root element of every sub-tree is not greater than any of the elements in the sub-tree below it. Like the heap, a Cartesian Tree is also a recursive structure. We show a linear time algorithm to build a cartesian tree from an input array. The difference between a cartesian tree and heap is that the former preserves the relative order of elements in the input array while the latter does not.

The Breadth First Search (BFS) ordered tree traversal. Blue arrows are the graph edges and red arrows indicate the order in which nodes are traversed in BFS order.

There are some common queries that are used almost everywhere, but they seem to be not executed very cleverly by most (all??) SQL execution ...

Blue arrows indicate edges, and red arrows indicate the order of traversal. The numbers indicate when the traversal happened. Binary Tree Traversal is a specialized form of General Tree traversal, where the notion of in-order tree traversal is well defined.

Advanced Data Structures (6.851). An awesome place to be!! http://courses.csail.mit.edu/6.851/ http://courses.csail.mit.edu/6.851/spring12/lectures/

Advanced Data Structures (6.851). An awesome place to be!! http://courses.csail.mit.edu/6.851/ http://courses.csail.mit.edu/6.851/spring12/lectures/

The Depth First Search (DFS) ordered tree traversal. Blue arrows are the graph edges and red arrows indicate the order in which nodes are traversed in DFS order. The number near each red arrow indicates the order in which the edges are traversed in DFS order.

Blue arrows indicate edges, and red arrows indicate the order of traversal. The numbers indicate when the traversal happened. Given the definitions of each of the tree traversals, try to reason why in-order traversal doesn't exist for general (non-binary) trees.