6 Matching Annotations
 Nov 2019

en.wikipedia.org en.wikipedia.org

In summary, ropes are preferable when the data is large and modified often.

 Oct 2019

www.cs.umd.edu www.cs.umd.edu

Thus the lessonto be learned is that when designing algorithms that operate on trees, it is important to be most efficienton the bottommost levels of the tree (as BuildHeap is) since that is where most of the weight of the treeresides.


typeocaml.com typeocaml.com

Merge is a recursive operation.

In order to maintain this property, each node has a rank, which indidates the length of the path between the node and the right most leaf. For example,
Rank  https://en.wikipedia.org/wiki/Leftist_tree#Svalue
Rank of a node, is the distance from that node to the nearest leaf in the subtree rooted at that node.

The relationship of left child and right child is not important, so the two child slots in the array for a root can be fully used. (Can we use array to implement a binary search tree?)

unfortunately we cannot have it in pure functional world where mutable array is not recommended.
