Editing Size Balanced Tree

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 1: Line 1:
A '''size balanced tree''' ('''SBT''') is a [[self-balancing binary search tree]] (SBBST) first published by Chinese student Qifeng Chen in 2007. The tree is rebalanced by examining the sizes of each node's subtrees. It is not to be confused with [https://en.wikipedia.org/wiki/Weight-balanced_tree weight-balanced trees], which have a slightly different set of balancing properties to be maintained.
+
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."<ref>Chen, Qifeng. [http://www.scribd.com/doc/3072015/ "Size Balanced Tree"], Guandong, China, 29 December 2006.</ref>
 
+
The only extra piece of information that needs to be stored at each node is the size of the subtree (compared to "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 that implement an [[order statistic tree]]. It also supports the 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."<ref>Chen, Qifeng. [http://www.scribd.com/doc/3072015/ "Size Balanced Tree"], Guandong, China, 29 December 2006.</ref>
+
  
 
==Properties==
 
==Properties==

Please note that all contributions to PEGWiki are considered to be released under the Attribution 3.0 Unported (see PEGWiki:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

Cancel | Editing help (opens in new window)