Editing Size Balanced Tree
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]] | + | 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." |
− | + | ||
− | + | ||
==Properties== | ==Properties== | ||
− | The size balanced tree examines each node's size (i.e. the number of nodes | + | 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> | ||
− | + | 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> | ||
− | + | right-rotate(t): | |
k ← t.left | k ← t.left | ||
t.left ← k.right | t.left ← k.right | ||
Line 162: | Line 160: | ||
done | done | ||
− | maintain(t.left, FALSE) | + | maintain(t.left, FALSE) //maintain the left subtree |
− | maintain(t.right, TRUE) | + | maintain(t.right, TRUE) //maintain the right subtree |
− | maintain(t, TRUE) | + | maintain(t, TRUE) //maintain the whole tree |
− | maintain(t, FALSE) | + | maintain(t, FALSE) //maintain the whole tree |
</pre> | </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). | 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). | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |