Small questions on data structure

Question

Hi, I'm trying to search the parent of a node with Kruskal's algorithm. My program works just fine, but I think I have heard of a method to improve the speed of the algorithm by reconstructing the tree while searching for the parent node and connecting it to the parent node. I'm pretty sure that I've heard of this somewhere, maybe in a lecture. Can anyone refresh my memory?

And also, given a number of arrays, when searching for the minimum and the maximum value from a certain section of an array, what is the name of the tree that can calculate the minimum/maximum value from the array by making a binary tree that has the minimum/maximum value of each array in O(log N)?

Answer 1

Concerning your second question: I think you're talking about a heap. A heap can retrieve you minimum or maximum in O(1) and delete it in O(log n).

However there are some sophisticated data structures, that are meant to handle complete lists (i.e. they are not designed for min/max acces in particular). These also support access to minimum and maximum simultaneously. Some prominent examples:

• Red-Black-Tree
• B-Tree (amortized O(log n))
• Splay-Tree (amortized O(log n))

Concerning your first question: Kruskals algorithm is used to compute a minimum spanning tree. But since you mention the "parent node" I assume that your considered structure is already a tree. But if the structure is already a tree, Kruskals algorithm just returns the tree itself. Could you maybe clarify what you mean by "parent node"

Answer 2

For the first question, you are looking for the Disjoint-set data structure.

For the second question, I assume your asking about range-minimum/maximum queries. The data structure for that is the Cartesian Tree.