Difference between revisions of "Size Balanced Tree"

From PEGWiki
Jump to: navigation, search
(Added Rotations)
(Added maintenance method)
Line 1: Line 1:
−
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 weights in treaps or colours in red–black tress), this makes it very convenient to implement the ''select'' and ''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."
+
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 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 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>
−
*<math>size(T.right) \ge size(T.left.left), size(T.left.right)</math>
+
#<math>size(T.right) \ge size(T.left.left), size(T.left.right)</math>
  
 
In other words, each child node of <math>T</math> is not smaller in size than the child nodes of its sibling. Clearly, we should consider the sizes of nonexistent children and siblings to be 0.
 
In other words, each child node of <math>T</math> is not smaller in size than the child nodes of its sibling. Clearly, we should consider the sizes of nonexistent children and siblings to be 0.
Line 25: Line 25:
  
 
==Rotations==
 
==Rotations==
−
The rotations of SBTs are analogous to those in other self-balancing BSTs.
+
The rotations of SBTs are analogous to those in other self-balancing binary search trees.
  
 
<pre>
 
<pre>
Line 57: Line 57:
 
     t &larr; k
 
     t &larr; k
 
</pre>
 
</pre>
 +
 +
==Maintenance==
 +
After insertions and deletions, the new sizes of subtrees may violate the two properties above. Thus, we define a procedure <code>maintain(T)</code> to rebalance the SBT rooted at the node <math>T</math>. This should be called with the precondition that <math>T</math>'s children are already SBTs themselves. Since property 1 and 2 are symmetrical, we will only discuss property 1.
 +
 +
There are 4 cases to consider when rebalancing.
 +
 +
*'''Case 1''': <math>size(T.left) < size\left(T.right.left\right)</math>
 +
:Perhaps after inserting a value to <math>T.right</math>, the scenario below (figure 1) may occur, leading to <math>size(L) < size\left(C\right)</math>.
 +
:To fix this, we first perform a <code>right-rotate</code> on <math>T.right</math> (figure 2) and then a <code>left-rotate</code> on <math>T</math> (figure 3).
 +
<pre>
 +
    Fig. 1:                Fig. 2:                  Fig. 3:   
 +
  insert(R,v)          right-rotate(R)            left-rotate(T)
 +
 +
      T                      T                        C     
 +
      / \                    / \                      / \     
 +
    /  \                  /  \                    /  \   
 +
    L    R                L    C                  T    R   
 +
  / \  / \              / \  / \                / \  / \ 
 +
  A  B C  D            A  B E  R              L  E F  D 
 +
      / \                        / \            / \         
 +
      E  F                      F  D          A  B         
 +
</pre>
 +
:After these operations, the properties of the entire tree in figure 3 becomes unpredictable. Luckily, the subtrees <math>A, B, D, E, F, L</math> are still SBTs. Thus, we can recursively call <code>maintain</code> on subtrees <math>R</math> and <math>T</math> to take care of them.
 +
:Now that all of the subtrees are SBTs, we still have to make sure that the root node <math>C</math> satisfies the SBT properties. So, we call <code>maintain</code> one last time on root node <math>C</math>.
 +
 +
*'''Case 2''': <math>size(T.left) < size\left(T.right.right\right)</math>
 +
:Perhaps after inserting a value to <math>T.right</math>, the scenario below (figure 4) may occur, leading to <math>size(L) < size\left(D\right)</math>. This is similar to case 1, except that instead of going below <math>C</math>, <math>E</math> and <math>F</math> instead goes below <math>D</math>. We can omit them from the diagram.
 +
:Fixing this, we will perform a <code>left-rotate</code> on the root node <math>T</math>, obtaining the structure in figure 5.
 +
<pre>
 +
    Fig. 4:                Fig. 5: 
 +
  insert(R,v)          left-rotate(T)
 +
      T                      R         
 +
      / \                    / \         
 +
    /  \                  /  \       
 +
    L    R                T    D       
 +
  / \  / \              / \           
 +
  A  B C  D            L  C           
 +
                        / \             
 +
                        A  B             
 +
</pre>
 +
:After this, the tree rooted at R is still not yet a SBT because <math>size(C) < size\left(A\right)</math> or <math>size(C) < size\left(B\right)</math> may be true. So, we continue to call <code>maintain</code> on <math>T</math>.
 +
: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.left\right)</math>
 +
:Symmetrical to case 2.
 +
*'''Case 4''': <math>size(T.right) < size\left(T.left.right\right)</math>
 +
:Symmetrical to case 1.

Revision as of 00:28, 20 August 2014

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

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 T in the tree satisfies the following two properties:

  1. size(T.left) \ge size(T.right.left), size(T.right.right)
  2. size(T.right) \ge size(T.left.left), size(T.left.right)

In other words, each child node of T is not smaller in size than the child nodes of its sibling. Clearly, we should consider the sizes of nonexistent children and siblings to be 0.

Consider the following example where T is the node in question, L, R are its child nodes, and A, B, C, D are subtrees which also satisfy the above SBT properties on their own. 

       T
      / \
     /   \
    L     R
   / \   / \
  A   B C   D

Then, the node T must satisfy:

  • size(L) \ge size(C), size(D)
  • size(R) \ge size(A), size(B)

Rotations

The rotations of SBTs are analogous to those in other self-balancing binary search trees. 

  -------------    Right Rotation     ------------
  |    Q      |   --------------->    |     P    |
  |   / \     |                       |    / \   |
  -- P   C    |                       |   A   Q --
    / \    <---     Left Rotation     --->   / \  
   A   B          <---------------          B   C

Left Rotation

left-rotate(t):
    k ← t.right
    t.right ← k.left
    k.left ← t
    k.size ← t.size
    t.size ← t.left.size + t.right.size + 1
    t ← k

Right Rotation

right-rotate(t):
    k ← t.left
    t.left ← k.right
    k.right ← t
    k.size ← t.size
    t.size ← t.left.size + t.right.size + 1
    t ← k

Maintenance

After insertions and deletions, the new sizes of subtrees may violate the two properties above. Thus, we define a procedure maintain(T) to rebalance the SBT rooted at the node T. This should be called with the precondition that T's children are already SBTs themselves. Since property 1 and 2 are symmetrical, we will only discuss property 1.

There are 4 cases to consider when rebalancing.

  • Case 1: size(T.left) < size\left(T.right.left\right)
Perhaps after inserting a value to T.right, the scenario below (figure 1) may occur, leading to size(L) < size\left(C\right).
To fix this, we first perform a right-rotate on T.right (figure 2) and then a left-rotate on T (figure 3).
    Fig. 1:                Fig. 2:                   Fig. 3:    
  insert(R,v)          right-rotate(R)            left-rotate(T)

       T                      T                         C       
      / \                    / \                       / \      
     /   \                  /   \                     /   \     
    L     R                L     C                   T     R    
   / \   / \              / \   / \                 / \   / \   
  A   B C   D            A   B E   R               L   E F   D  
       / \                        / \             / \           
      E   F                      F   D           A   B
After these operations, the properties of the entire tree in figure 3 becomes unpredictable. Luckily, the subtrees A, B, D, E, F, L are still SBTs. Thus, we can recursively call maintain on subtrees R and T to take care of them.
Now that all of the subtrees are SBTs, we still have to make sure that the root node C satisfies the SBT properties. So, we call maintain one last time on root node C.
  • Case 2: size(T.left) < size\left(T.right.right\right)
Perhaps after inserting a value to T.right, the scenario below (figure 4) may occur, leading to size(L) < size\left(D\right). This is similar to case 1, except that instead of going below C, E and F instead goes below D. We can omit them from the diagram.
Fixing this, we will perform a left-rotate on the root node T, obtaining the structure in figure 5.
    Fig. 4:                Fig. 5:   
  insert(R,v)           left-rotate(T)
       T                       R           
      / \                     / \          
     /   \                   /   \         
    L     R                 T     D        
   / \   / \               / \             
  A   B C   D             L   C            
                         / \               
                        A   B
After this, the tree rooted at R is still not yet a SBT because size(C) < size\left(A\right) or size(C) < size\left(B\right) may be true. So, we continue to call maintain on T.
Now that we have satisfied the precondition of making R's subtrees SBTs, we may call maintain on R itself.
  • Case 3: size(T.right) < size\left(T.left.left\right)
Symmetrical to case 2.
  • Case 4: size(T.right) < size\left(T.left.right\right)
Symmetrical to case 1.
Retrieved from "http://wcipeg.com/wiki/index.php?title=Size_Balanced_Tree&oldid=1807"