NAME

Tree::SizeBalanced - Size balanced binary search tree (XS implementation)

Handy for in-memory realtime ranking systems.

SYNOPSIS

  use Tree::SizeBalanced; # use $tree = Tree::SizeBalanced::int_any->new
  use Tree::SizeBalanced qw(:long); # use $tree = sbtree_int_any;
  use Tree::SizeBalanced qw(:short); # use $tree = sbtreeia;
  use Tree::SizeBalanced qw(:all); # export :short and :long

  my $tree_map_any_any = sbtree_any_any { length($b) <=> length($a) };
  my $tree_map_any_any = sbtreeaa { length($b) <=> length($a) }; # shorter form
  my $tree_map_any_any = Tree::SizeBalanced::any_any->new
    sub { length($b) <=> length($a) }; # full form
  # tree map with any scalars as keys

  my $tree_set_num = sbtree_num_void;
  my $tree_set_num = sbtreen; # shorter form
  my $tree_set_num = Tree::SizeBalanced::num_void->new; # full form
  # or set version.
  #  This one use numeric values (floating point numbers) as keys

  my $tree = sbtree_int_any;
  my $tree = sbtreeia; # shorter form
  my $tree = Tree::SizeBalanced::int_any->new; # full form
  # tree map (key value pairs)
  #  the keys are signed integers
  #  the values are any scalars

  $tree->insert(1, {a => 3});

  ...

  my $count = $tree->count_lt(25);
  # how many entries in the tree whose key is less than 25
  my $count = $tree->count_gt(25);
  # how many entries in the tree whose key is greater than 25

  ($key, $value) = $tree->skip_l(23);
  $key = $tree->skip_l(23);
  # Get the first (smallest) entry whose key is greater than 23

  ($key, $value) = $tree->skip_g(23);
  $key = $tree->skip_g(23);
  # Get the first (largest) entry whose key is less than 23

  ($key, $value) = $tree->find_min;
  $key = $tree->find_min;
  ($key, $value) = $tree->find_max;
  $key = $tree->find_max;

  ($k1, $v1, $k2, $v2) = $tree->find_min(2);
  ($k1, $v1, $k2, $v2, $k3, $v3) = $tree->find_min(3);
  ($k1, $v1, $k2, $v2, $k3, $v3, ...) = $tree->find_min(-1);

  ($k1, $v1, ...= $tree->find_lt_gt($lower_bound, $upper_bound);

  ...

  $tree->delete(1);

DESCRIPTION

Quoted from http://wcipeg.com/wiki/Size_Balanced_Tree:

> A size balanced tree (SBT) is a self-balancing binary search tree (BBST) first published by Chinese student Qifeng Chen in 2007. The tree is rebalanced by examining the sizes of each node's subtrees. Its abbreviation resulted in many nicknames given by Chinese informatics competitors, including "sha bi" tree (Chinese: 傻屄树; pinyin: shǎ bī shù; literally meaning "dumb cunt tree") and "super BT", which is a homophone to the Chinese term for snot (Chinese: 鼻涕; pinyin: bítì) suggesting that it is messy to implement. Contrary to what its nicknames suggest, this data structure can be very useful, and is also known to be easy to implement. Since the only extra piece of information that needs to be stored is sizes of the nodes (instead of other "useless" fields such as randomized weights in treaps or colours in red–black tress), this makes it very convenient to implement the select-by-rank and get-rank operations (easily transforming it into an order statistic tree). It supports standard binary search tree operations such as insertion, deletion, and searching in O(log n) time. According to Chen's paper, "it works much faster than many other famous BSTs due to the tendency of a perfect BST in practice."

For performance consideration, this module provides trees with many stricter types.

If you choose any scalar as the key type, you must provide a comparing sub. The comparing sub should exammed localized $a and $b (or $::a and $::b if there are introduced lexical <$a> and <$b> right outside the sub). And if your comparing sub using an indirect way to judge the size of the keys, don't do anything that will change the judge result. Or, the tree will be confused and give you incorrect results.

If you put more than one entries with equal-sized keys, the insertion order is preserved by treating the first one as the smallest one among them.

PS. Qifeng Chen is 陈启峰 in simplified Chinese.

This module has been tested on perl version 5.8.9, 5.10.1, 5.12.5, 5.14.4, 5.16.3, 5.18.4, 5.20.3, 5.22.2

EXPORT

All exported subs are different style ways to create new trees.

(nothing)

Without importing anything, you can use the full form to obtain a new tree:

  my $tree = Tree::SizeBalanced::str_any->new;

:long

With the long form:

  my $tree = sbtree_any_str { length($a) <=> length($b) || $a cmp $b };

:short

With the short form:

  my $tree = sbtreei;

:all = :short + :long

Different trees with different types

Tree::SizeBalanced::int_void

Tree set with key type signed integers (32bits or 64bits according to your perl version).

$tree = Tree::SizeBalanced::int_void->new

$tree = sbtree_int_void

$tree = sbtreei

Creat a new empty tree.

$tree->insert($key)

$tree->insert_after($key)

Insert an entry into the tree. If there are any entries with the same key size, insert the new one after them.

$tree->insert_before($key)

Insert an entry into the tree. If there are any entries with the same key size, insert the new one before them.

$tree->delete($key)

$tree->delete_last($key)

Delete one entry whose key is equal to $key. If there ary more than one entry with the same key size, delete the last inserted one.

$tree->delete_first($key)

Delete one entry whose key is equal to $key. If there ary more than one entry with the same key size, delete the first inserted one.

$size = $tree->size

Get the number of entries in the tree

$key or ($key1, $key2, ...) = $tree->find($key, $limit=1)

$key or ($key1, $key2, ...) = $tree->find_first($key, $limit=1)

Get entries with key sizes equal to $key, from the first inserted one to the last inserted one.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $key2, ...) = $tree->find_last($key, $limit=1)

Get entries with key sizes equal to $key, from the last inserted one to the first inserted one.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $key2, ...) = $tree->find_lt($key, $limit=1)

Get entries, whose keys are smaller than $key, from the largest entry.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $key2, ...) = $tree->find_le($key, $limit=1)

Get entries, whose keys are smaller than or equal to $key, from the largest entry.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $key2, ...) = $tree->find_gt($key, $limit=1)

Get entries, whose keys are greater than $key, from the smallest one.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $key2, ...) = $tree->find_ge($key, $limit=1)

Get entries, whose keys are greater than or equal to $key, from the smallest one.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $key2, ...) = $tree->find_gt_lt($lower_key, $upper_key)

Get entries, whose keys are greater than $lower_key and smaller than $upper_key, from the smallest one to the largest one.

$key or ($key1, $key2, ...) = $tree->find_gt_le($lower_key, $upper_key)

Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, from the smallest one to the largest one.

$key or ($key1, $key2, ...) = $tree->find_ge_lt($lower_key, $upper_key)

Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, from the smallest one to the largest one.

$key or ($key1, $key2, ...) = $tree->find_ge_le($lower_key, $upper_key)

Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, from the smallest one to the largest one.

$key or ($key1, $key2, ...) = $tree->find_min($limit=1)

Get entries from the one with smallest key. If there are more than one entries with smallest key, begin from the first inserted one.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $key2, ...) = $tree->find_max($limit=1)

Get entries from the one with largest key. If there are more than one entries with smallest key, begin from the last inserted one.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $key2, ...) = &tree->skip_l($offset, $limit=1)

Get the first entry from one with the smallest key after skipping $offset entries.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $key2, ...) = &tree->skip_g($offset, $limit=1)

Get the first entry from one with the largest key after skipping $offset entries.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$count = $tree->count_lt($key)

Get the number of entries whose keys are smaller than $key.

$count = $tree->count_le($key)

Get the number of entries whose keys are smaller than or equal to $key.

$count = $tree->count_gt($key)

Get the number of entries whose keys are greater than $key.

$count = $tree->count_ge($key)

Get the number of entries whose keys are greater than or equal to $key.

$dump_str = $tree->dump

Get a string which represent the whole tree structure. For debug use.

($order_consistent, $size_consistent, $balanced) = $tree->check

Check the tree property. For debug use.

$ever_height = $tree->ever_height

Get the maximum height the tree has ever been. For debug use

Tree::SizeBalanced::int_int

Tree map with key type signed integers (32bits or 64bits according to your perl version) and value type signed integers (32bits or 64bits according to your perl version).

$tree = Tree::SizeBalanced::int_int->new

$tree = sbtree_int_int

$tree = sbtreeii

Creat a new empty tree.

$tree->insert($key, $value)

$tree->insert_after($key, $value)

Insert an entry into the tree. If there are any entries with the same key size, insert the new one after them.

$tree->insert_before($key, $value)

Insert an entry into the tree. If there are any entries with the same key size, insert the new one before them.

$tree->delete($key)

$tree->delete_last($key)

Delete one entry whose key is equal to $key. If there ary more than one entry with the same key size, delete the last inserted one.

$tree->delete_first($key)

Delete one entry whose key is equal to $key. If there ary more than one entry with the same key size, delete the first inserted one.

$size = $tree->size

Get the number of entries in the tree

$key or ($key1, $value1, $key2, $value2, ...) = $tree->find($key, $limit=1)

$key or ($key1, $value1, $key2, $value2, ...) = $tree->find_first($key, $limit=1)

Get entries with key sizes equal to $key, from the first inserted one to the last inserted one.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $value1, $key2, $value2, ...) = $tree->find_last($key, $limit=1)

Get entries with key sizes equal to $key, from the last inserted one to the first inserted one.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $value1, $key2, $value2, ...) = $tree->find_lt($key, $limit=1)

Get entries, whose keys are smaller than $key, from the largest entry.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $value1, $key2, $value2, ...) = $tree->find_le($key, $limit=1)

Get entries, whose keys are smaller than or equal to $key, from the largest entry.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt($key, $limit=1)

Get entries, whose keys are greater than $key, from the smallest one.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge($key, $limit=1)

Get entries, whose keys are greater than or equal to $key, from the smallest one.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_lt($lower_key, $upper_key)

Get entries, whose keys are greater than $lower_key and smaller than $upper_key, from the smallest one to the largest one.

$key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_le($lower_key, $upper_key)

Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, from the smallest one to the largest one.

$key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_lt($lower_key, $upper_key)

Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, from the smallest one to the largest one.

$key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_le($lower_key, $upper_key)

Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, from the smallest one to the largest one.

$key or ($key1, $value1, $key2, $value2, ...) = $tree->find_min($limit=1)

Get entries from the one with smallest key. If there are more than one entries with smallest key, begin from the first inserted one.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $value1, $key2, $value2, ...) = $tree->find_max($limit=1)

Get entries from the one with largest key. If there are more than one entries with smallest key, begin from the last inserted one.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_l($offset, $limit=1)

Get the first entry from one with the smallest key after skipping $offset entries.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_g($offset, $limit=1)

Get the first entry from one with the largest key after skipping $offset entries.

The optional $limit (default 1) indicates the maximum entry number you will get, $limit=-1 means unlimited.

$count = $tree->count_lt($key)

Get the number of entries whose keys are smaller than $key.

$count = $tree->count_le($key)

Get the number of entries whose keys are smaller than or equal to $key.

$count = $tree->count_gt($key)

Get the number of entries whose keys are greater than $key.

$count = $tree->count_ge($key)

Get the number of entries whose keys are greater than or equal to $key.

$dump_str = $tree->dump

Get a string which represent the whole tree structure. For debug use.

($order_consistent, $size_consistent, $balanced) = $tree->check

Check the tree property. For debug use.

$ever_height = $tree->ever_height

Get the maximum height the tree has ever been. For debug use

Tree::SizeBalanced::int_num

Tree map with key type signed integers (32bits or 64bits according to your perl version) and value type numeric numbers (floating point numbers).

$tree = Tree::SizeBalanced::int_num->new

$tree = sbtree_int_num

$tree = sbtreein