Left tree

from Wikipedia, the free encyclopedia

A left tree or link sheap is a binary tree that can be used as a priority queue . This data structure is an invention of Clark Allan Crane and uses a heap structure . In contrast to balanced binary trees, left-hand trees do not require that each path be logarithmic at most. It is sufficient that there is a logarithmically long path to a leaf from each node and that this is known. Left trees can be merged efficiently.

definition

A left tree is defined by a set of totally ordered keys. The order defined on the keys determines the priority of a key.

  • A node with distance 0 and a key of minimum priority is a left tree.
  • A node with two left trees as children is a left tree if:
    • Its key has at least as high priority as its children's keys (heap property).
    • The left child has at least as great a distance as the right child.
    • Its distance is exactly 1 greater than the distance of the right child.

The definition implies that the distance measures the length of the shortest path to a leaf. If you always follow the child on the right in a left-hand tree, then you follow such a shortest path.

Operations

A links tree with n keys supports the following operations guaranteed in O ( log n ) time:

  • insert - to insert an element,
  • extractMin - for returning and removing an element with the highest priority and
  • merge - to merge two heaps.

Algorithms

Note that a node with distance 0 represents an empty left tree. In one implementation, this is usually represented as a null pointer.

Merge

This operation is intended to merge two left trees into a new left tree.

Let K be the tree with lower priority and G the tree with higher priority (if they have the same priority, decide arbitrarily). The procedure can then be described recursively as follows:

  1. If both trees are 0 apart, immediately return G and skip the following steps.
  2. If G has a right child with distance 0, set K as the right child of G. Otherwise merge the right child of G with K and set the resulting tree as the right child of G.
  3. If after step 2 the right child of G has a greater distance than the left child of G, swap the two children.
  4. The new root is G. The distance of the new root is 1 plus the distance of the child on the right.

The steps guarantee one after the other the properties that were required in the definition for the resulting left tree.

Insert

To insert a new key, create a new node with the desired key and merge the newly created left tree with the old tree. The newly created node should have two left trees with distance 0 as children before merging.

Extract the next item (extractMin)

Because of the heap property, the key with the highest priority is always at the root and can therefore be read directly. The children of the root are merged and the result is set as the new root. This operation is only valid if the root has a distance of at least 1.

running time

  • The merging of two left-hand trees with a total of n nodes using merge requires at most O ( log n ) time:

There is a constant amount of work being done in each step of the recursion. Each recursive call is made on trees whose distances are, in total, exactly one shorter. The recursion ends at the latest when the sum of the distances is one. So the running time is limited by the sum of the distances. Since the distances denote the length of the shortest path because of the definition of left trees, and the length of the shortest path in a binary tree with k nodes is at most log 2 (k) + 1 , the bound follows.

  • The runtime for insert and extractMin is limited by a constant plus the time to merge two left trees.

literature

  • Thomas Ottman / Peter Widmayer: Algorithms and Data Structures. 4th edition. Spectrum Academic Publishing House, Heidelberg / Berlin 2002, ISBN 978-3-8274-1029-0 (Chapter 6.1)