Module aptos_types::proof::position

This module provides an abstraction for positioning a node in a binary tree, A Position uniquely identifies the location of a node

In this implementation, Position is represented by the in-order-traversal sequence number of the node. The process of locating a node and jumping between nodes is done through in-order position calculation, which can be done with bit manipulation.

For example

     3
    /  \
   /    \
  1      5 <-[Node index, a.k.a, Position]
 / \    / \
0   2  4   6

0   1  2   3 <[Leaf index]

Note1: The in-order-traversal counts from 0 Note2: The level of tree counts from leaf level, start from 0 Note3: The leaf index starting from left-most leaf, starts from 0

Structs

AncestorIterator

AncestorIterator generates current position and moves itself to its parent position for each iteration.

AncestorSiblingIterator

AncestorSiblingIterator generates current sibling position and moves itself to its parent position for each iteration.

FrozenSubTreeIterator

Traverse leaves from left to right in groups that forms full subtrees, yielding root positions of such subtrees. Note that each 1-bit in num_leaves corresponds to a full subtree. For example, in the below tree of 5=0b101 leaves, the two 1-bits corresponds to Fzn2 and L4 accordingly.

FrozenSubtreeSiblingIterator

Given an accumulator of size current_num_leaves, FrozenSubtreeSiblingIterator yields the positions of required subtrees if we want to append these subtrees to the existing accumulator to generate a bigger one of size new_num_leaves.

Position

Enums

NodeDirection

Functions

inorder_to_postorder

Given node, an index in an in-order traversal of a perfect binary tree, what order would the node be visited in in post-order traversal? For example, consider this tree of in-order nodes.

postorder_to_inorder