Struct TreeNode

pub struct TreeNode {
    pub height: usize,
    pub leaves_count: i64,
    /* private fields */
}

Node of a binary tree.

This binary tree implementation has limited functionality and is tailored specifically for the PathORAM use case.

Fields

height: usize

leaves_count: i64

Implementations

impl TreeNode

pub fn new(value: i64) -> Self

pub fn create_tree(n: i64) -> TreeNode

Create and return a binary tree of the given size

Invariants

n must be equal to (2^k)-1 for any k >= 0 In other words, n must be a power of two, minus one.

impl TreeNode

pub fn is_leaf(&self) -> bool

Return true if this node is a leaf

pub fn leaves(&mut self) -> Vec<i64>

Return the values of the leaves in the tree

pub fn path_to_node(&self, x: i64) -> Vec<i64>

Return the nodes on the path from the root to the node with value x

pub fn path(&mut self, x: i64) -> Arc<Vec<i64>>

Return the path from the root to the xth leaf (0-based). Path from leaf to root is called P(x) in Path ORAM

pub fn pathl(&mut self, x: i64, level: usize) -> i64

Get the node at level l from the path from root to xth leaf (0-based) Also called P(x, l) in Path ORAM level=0 => root level=L => leaves