| Name : perl-Tree-SizeBalanced
| |
| Version : 2.006002
| Vendor : obs://build_opensuse_org/devel:languages:perl
|
| Release : lp156.1.1
| Date : 2024-07-03 19:18:06
|
| Group : Development/Libraries/Perl
| Source RPM : perl-Tree-SizeBalanced-2.006002-lp156.1.1.src.rpm
|
| Size : 0.73 MB
| |
| Packager : https://www_suse_com/
| |
| Summary : Size balanced binary search tree (XS implementation)
|
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
|
RPM found in directory: /packages/linux-pbone/ftp5.gwdg.de/pub/opensuse/repositories/devel:/languages:/perl:/CPAN-T/15.6/x86_64 |
