Struct BalancedBinaryTree

pub struct BalancedBinaryTree<K: Ord, M: ActedMonoid> { /* private fields */ }

平衡二分木

Implementations

impl<K: Ord + Clone, M: ActedMonoid> BalancedBinaryTree<K, M>

pub fn insert_lower(&mut self, key: K, val: M::Val)

key, val を挿入する（lowerbound 版）

• 既存の同一 key は右側（>=）に送るので，新要素は「同一 key の先頭」に入る

pub fn insert_upper(&mut self, key: K, val: M::Val)

key, val を挿入する（upperbound 版）

• 既存の同一 key は左側（<=）に送るので，新要素は「同一 key の末尾」に入る

pub fn insert_unique(&mut self, key: K, val: M::Val) -> bool

key がまだ存在しないときだけ (key, val) を挿入する

• 返り値: 挿入できたら true, 既に存在していたら false

pub fn remove(&mut self, key: &K) -> bool

key をもつ要素を削除する（存在すれば全て削除）

• 返り値: 1 個以上削除できたら true

pub fn get_range<R: RangeBounds<K> + Debug>(&mut self, range: R) -> M::Val

区間（key の範囲）の集約値を返す

pub fn apply<R: RangeBounds<K> + Debug>(&mut self, range: R, act: M::Act)

区間（key の範囲）に作用を適用する

pub fn is_empty(&self) -> bool

空であるか判定する

pub fn len(&self) -> usize

要素数をカウントする

Trait Implementations

impl<K: Ord, M: ActedMonoid> Default for BalancedBinaryTree<K, M>

fn default() -> Self

Returns the “default value” for a type.

impl<K, M> ShowBinaryTree<Ptr> for BalancedBinaryTree<K, M>

where K: Ord + Debug, M: ActedMonoid, M::Val: Debug, M::Act: Debug,

fn get_root(&self) -> Option<Ptr>

<required> 根を取得する

fn get_left(&self, ptr: &Ptr) -> Option<Ptr>

<required> 左の子のポインタを取得する

fn get_right(&self, ptr: &Ptr) -> Option<Ptr>

<required> 右の子のポインタを取得する

fn print_node(&self, ptr: &Ptr) -> String

<required> ノードの値を表示する

fn print_inner(&self, ptr: P, fill: &mut Vec<&'static str>, last: &'static str)

再帰的にprintを行う

fn print_as_binary_tree(&self)

2分木としてフォーマットする