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]] 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 in dynamic order statistics problems. It supports standard binary search tree operations such as insertion, deletion, and searching in O(log ''n'') time. According to Chen's paper, "this is the fastest known advanced binary search tree to date." |
− | | + | |
− | 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== |
− | The size balanced tree examines each node's size (i.e. the number of nodes below it in the subtree) to determine when rotations should be performed. Each node <math>T</math> in the tree satisfies the following two properties: | + | The size balanced tree examines each node's size (i.e. the number of nodes in the subtree rooted at that node) to determine when rotations should be performed. Each node <math>T</math> in the tree satisfies the following two properties: |
| | | |
| #<math>size(T.left) \ge size(T.right.left), size(T.right.right)</math> | | #<math>size(T.left) \ge size(T.right.left), size(T.right.right)</math> |
Line 40: |
Line 38: |
| ===Left Rotation=== | | ===Left Rotation=== |
| <pre> | | <pre> |
− | def left-rotate(t):
| + | left-rotate(t): |
| k ← t.right | | k ← t.right |
| t.right ← k.left | | t.right ← k.left |
Line 51: |
Line 49: |
| ===Right Rotation=== | | ===Right Rotation=== |
| <pre> | | <pre> |
− | def right-rotate(t):
| + | right-rotate(t): |
| k ← t.left | | k ← t.left |
| t.left ← k.right | | t.left ← k.right |
Line 102: |
Line 100: |
| :Now that we have satisfied the precondition of making <math>R</math>'s subtrees SBTs, we may call <code>maintain</code> on <math>R</math> itself. | | :Now that we have satisfied the precondition of making <math>R</math>'s subtrees SBTs, we may call <code>maintain</code> on <math>R</math> itself. |
| | | |
− | *'''Case 3''': <math>size(T.right) < size\left(T.left.right\right)</math> | + | *'''Case 3''': <math>size(T.right) < size\left(T.left.left\right)</math> |
| + | :Symmetrical to case 2. |
| + | *'''Case 4''': <math>size(T.right) < size\left(T.left.right\right)</math> |
| :Symmetrical to case 1. | | :Symmetrical to case 1. |
− | *'''Case 4''': <math>size(T.right) < size\left(T.left.left\right)</math>
| |
− | :Symmetrical to case 2.
| |
− |
| |
− |
| |
− | With this casework being taken care of, it becomes straightforward to actually implement <code>maintain</code>.
| |
− | <pre>
| |
− | def maintain(t):
| |
− |
| |
− | if t.left.size < t.right.left.size: //case 1
| |
− | right-rotate(t.right)
| |
− | left-rotate(t)
| |
− | maintain(t.left)
| |
− | maintain(t.right)
| |
− | maintain(t)
| |
− |
| |
− | else if t.left.size < t.right.right.size: //case 2
| |
− | left-rotate(t)
| |
− | maintain(t.left)
| |
− | maintain(t)
| |
− |
| |
− | else if t.right.size < t.left.right.size: //case 1'
| |
− | left-rotate(t.left)
| |
− | right-rotate(t)
| |
− | maintain(t.left)
| |
− | maintain(t.right)
| |
− | maintain(t)
| |
− |
| |
− | else if t.right.size < t.left.left.size: //case 2'
| |
− | right-rotate(t)
| |
− | maintain(t.right)
| |
− | maintain(t)
| |
− | </pre>
| |
− |
| |
− |
| |
− | This pseudocode is slightly slow and redundant. Since we know that the two SBT properties will ''usually'' be satisfied, the following is an optimization.
| |
− | Simply add an extra boolean flag to the <code>maintain</code> parameters, indicating whether cases 1/2 or their symmetrical cases are being examined.
| |
− | If the flag is TRUE, then we examine cases 1 and 2, otherwise we examine cases 3 and 4. Doing so will eliminate many unnecessary comparisons.
| |
− |
| |
− | <pre>
| |
− | def maintain(t, flag):
| |
− |
| |
− | if flag:
| |
− | if t.left.size < t.right.left.size: //case 1
| |
− | right-rotate(t.right)
| |
− | left-rotate(t)
| |
− | else if t.left.size < t.right.right.size: //case 2
| |
− | left-rotate(t)
| |
− | else:
| |
− | done
| |
− | else:
| |
− | if t.right.size < t.left.right.size: //case 1'
| |
− | left-rotate(t.left)
| |
− | right-rotate(t)
| |
− | else if t.right.size < t.left.left.size: //case 2'
| |
− | right-rotate(t)
| |
− | else:
| |
− | done
| |
− |
| |
− | maintain(t.left, FALSE) //maintain the left subtree
| |
− | maintain(t.right, TRUE) //maintain the right subtree
| |
− | maintain(t, TRUE) //maintain the whole tree
| |
− | maintain(t, FALSE) //maintain the whole tree
| |
− | </pre>
| |
− |
| |
− | The proof for why <code>maintain(t.left, TRUE)</code> and <code>maintain(t.right, FALSE)</code> are unnecessary can be found in section 6 of Chen's paper. Furthermore, the running time of <code>maintain</code> is O(1) amortized (which means that you do not have to worry about it not terminating).
| |
− |
| |
− | ==Fundamental Operations==
| |
− |
| |
− | ===Searching===
| |
− | Searching in SBTs is exactly the same as searching in other binary search trees. The following iterative implementation will return a pointer to the node in the SBT rooted at <math>t</math> which has key <math>k</math>.
| |
− | <pre>
| |
− | def search(t, k):
| |
− | x ← t
| |
− | while x is not NIL:
| |
− | if k < x.key then x ← x.left
| |
− | else if x.key < k then x ← x.right
| |
− | else return x
| |
− | return NIL //key not found!
| |
− | </pre>
| |
− |
| |
− | ===Get Max/Min===
| |
− | The size of the SBT is already stored. These operations can thus be handled trivially by the <code>select</code> operation implemented in the section below.
| |
− |
| |
− | ===Iteration===
| |
− | Iterating a SBT is exactly the same as iterating a normal binary search tree (by repeatedly finding nodes' predecessors/successors).
| |
− |
| |
− | ===Insertion===
| |
− | Inserting into a SBT is very simple. The only difference from normal binary search trees is that it has an extra call to <code>maintain</code> at the end. The following recursive version will insert the node <math>x</math> into the SBT rooted at <math>t</math>.
| |
− | <pre>
| |
− | def insert(t, x):
| |
− | if x is NIL:
| |
− | t ← x
| |
− | else
| |
− | t.size ← t.size + 1
| |
− | if x.key < t.key:
| |
− | insert(t.left, x)
| |
− | else
| |
− | insert(t.right, x)
| |
− | maintain(t, x.key ≥ t.key)
| |
− | </pre>
| |
− |
| |
− | ===Deletion===
| |
− | Deletion is exactly the same as in normal binary search trees. It is not even necessary to call <code>maintain</code> afterwards. The proof for this is as follows: A SBT will have all of its properties before deletion. Even though we cannot guarantee that the SBT will retain its balanced properties after the insertion, we know for sure that its height (and thus, its running time) will not increase. Given this, it is clear that calling <code>maintain</code> after deleting is extraneous.
| |
− |
| |
− | ==Order Statistics==
| |
− | Since SBTs already conveniently store the <math>size</math> field to maintain balance, nothing else is needed to transform it into a fully-fledged order statistics tree.
| |
− |
| |
− | ===Select===
| |
− | The following function returns a pointer to the <math>i</math>th smallest element in the SBT rooted at <math>t</math>, where <math>i</math> is zero-indexed. To make this one-indexed, simply change "<code>r ← t.left.size</code>" to "<code>r ← t.left.size + 1</code>" and "<code>i - (r + 1)</code>" to "<code>i - r</code>".
| |
− |
| |
− | <pre>
| |
− | def select(t, i):
| |
− | r ← t.left.size
| |
− | if i = r:
| |
− | return t
| |
− | else if i < r:
| |
− | return select(t.left, i)
| |
− | else
| |
− | return select(t.right, i - (r + 1))
| |
− | </pre>
| |
− |
| |
− | ===Rank===
| |
− | Determining the rank of an element in a SBT is exactly the same as doing so for a regular binary search tree.
| |
− |
| |
− | ==References==
| |
− | <references/>
| |