Size Balanced Tree (SBT tree) finishing

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Do not want to use the Treap and Splay, then use SB tree to, ha ha, in fact, it is SB, ill.

Author Chen Qifeng to worship. Orz

The following is my collection to.

A, BST and its limitation



Two binary search tree (Binary Search Tree), also known as ordered two fork tree (ordered binary tree), ranking two fork tree (sorted binary tree), refers to a hollow tree or has the following properties of two binary tree:
1 if any node in the left subtree is not empty, then the left sub tree all nodes of the value was less than the root node; it'svalue,
2 any node in the right subtree is not empty, then the right subtree on all nodes of the value it was greater than the root node.value,
3 any node in the left, the right subtree is respectively two binary search tree.
4 no key value equivalent nodes;(no duplicate nodes).
Compared to the other two binary search tree data structure's advantage lies in the lookup, insertion of low time complexity. For O(log n)
However, disadvantage is the sequence to be inserted is ordered, it will degenerate into a single list! So the query time will be O(n)!
The solution has a lot of improved version of the two binary search trees can make the tree height is O (logn), such as SBT, AVL, red black tree, Treap
The red black tree and AVL is more complex, not suitable for use in the algorithm competition.

The basic idea of balance.:


Pseudo code right

Right-handed operation assumes the son left there.

Right-Rotate(t)
 k ← left[t]
 left[t] ← right[k]
 right[k] ← t
 s[k] ← s[t]
 s[t] ← s[left[t]] + s[right[t]] + 1
 t ← k


Pseudo code left

L operation assumes the existence right son.


Left-Rotate(t)
 k ← right[t]
 right[t] ← left[k]
 left[k] ← t
 s[k] ← s[t]
 s[t] ← s[left[t]] + s[right[t]] + 1
 t ← k


Two, SBT

Size Balanced Tree (SBT) is a kind of balance of two binary search trees, the tree size s[t] to maintain the balance of nature. It supports many dynamic operation, and in the O (log n) completion time.
In order to facilitate the discussion below,
We set
left [T] : Node T Zuo Erzi
right [T] : Node T right son
s [T] : The number of the root of a subtree of nodes with T (size))


Why SBT can keep balance?
Because for every node of t SBT, has the following properties:
Nature(a) s[ right[t] ]≥s[ left [ left[ t ] ] ], s[ right [ left[t] ] ]
Nature(b) s[ left[t] ]≥s[right[ right[t] ] ], s[ left[ right[t] ] ]

Namely. Each subtree size not less than its sibling subtrees of size. (for array to realize the tree is not familiar with the children's shoes, please put the translation of s[left [left[t]]] for s[t-> left-> left] the same, s[right [left[t]]] to s[ t->left->right ] )



Pictured above are s[A], s[B] ≤ s[R] and S[C],s[D] ≤s[L]

1 balance maintenance mantain

After performing a simple insertion, properties of a or B might not meet, so we need to adjust the SBT.



Maintain (T) Used to repair with T as the root of the SBT. Due to the nature of (a) and (b) is symmetric, only below the discussion on the properties of (a) repair.



Case 1: s[ Left[ Left[ T ] ]>s[ Right[ T ] ]

In the following figure, that is s[A]>s[R]


First perform the dextral (Right-Rotate (T)) available


There may be rotated tree still is not SBT, need to perform Maintain again(T)

Due to the change of L right son, therefore need to perform Maintain(L)

That is to say, the first implementation of a Right-Rotate (T), then Maintain (T) ensures that the T is SBT, then the implementation of Maintain (L), ensure that L is SBT

Case 2: s[ right[ left[ t ] ]>s[ right[ t ] ]

In the figure below, that is to say s[B]>s[R]


The first implementation of a Left-Rotate (L). The following diagram






Implementation of right-handed Right-Rotate (T), as shown in the following figure:


Then perform Maintain (L) and Maintain (T), to ensure that L and T is SBT
The implementation of Maintain (B)


Case 3: s[ right[ right[ t ] ] ]>s[ left[ t ] ]
The case 1 is symmetric. . . .

Case 4: s[ left[ right[ t ] ] ]>s[ left[ t ] ]

The case 2 is symmetric. .




Can write C+ + code is as follows, feeling than the pseudo code. .
void matain(int &t)  
    {  
        if(size[ left[ left[t] ] ] > size[ right[t] ] )  
        {  
            right_rotate(t);  
            matain(right[t]);  
            matain(t);  
        }  
        else if( size[ right[ left[t] ] ]>size[ right[t] ] )  
        {  
            left_rotate(left[t]);  
            right_rotate(t);  
            matain(left[t]);  
            matain(right[t]);  
            matain(t);  
        }  
        else if(size[ right[ right[t] ] ]>size[ left[t] ])  
        {  
            left_rotate(t);  
            matain(left[t]);  
            matain(t);  
        }  
        else if(size[ left[ right[t] ] ]>size[ left[t] ])  
        {  
            right_rotate(right[t]);  
            left_rotate(t);  
            matain(left[t]);  
            matain(right[t]);  
            matain(t);  
        }  
}


The maintenance after the operation, the next step is very simple.

2 into insert

Insert (t,v)
 If t=0 then
   t ← NEW-NODE(v)
 Else
   s[t] ← s[t]+1
   If v<key[t] then
     Simple-Insert(left[t],v)
   Else
     Simple-Insert(right[t],v)
   Maintain(t,v≥key[t])

Remove the 3 delete


If you delete a node is not found, then delete the last visited node and record.

Delete (t,v)
  If s[t]≤2 then
    record ← key[t]
    t ← left[t]+right[t]
    Exit
  s[t] ← s[t]-1
  If v=key[t] then
    Delete(left[t],v[t]+1)
    Key[t] ← record
    Maintain(t,true)
 Else
   If v<key[t] then
     Delete(left[t],v)
   Else
     Delete(right[t],v)
   Maintain(t,v<key[t])




Due to the nature of SBT (node T keywords are large, than all the nodes in its left subtree of keywords in the right subtree than in all the key words are small), the algorithm is very easy to understand.

4.Select operation

Return in the K position of the node (i.e., return to the root of T tree in the ranking for the K node. ). It includes large (Maximum) and small (Minimun), and is equivalent to Select (T, 1), take small equivalent to Select(t,s[t]).

Select(t,k)
       If k=s[left[t]]+1 then
              return key[t]
       If k<=s[left[t]] then
              return Select(left[t],k)
       Else
              return Select(right[t],k-1-s[left[t]])


5.Rank operation

Returns the V in t as the root of the tree in the rankings, the tree is smaller than the V size (Size) plus one.

Rank(t,v)
       If t=0 then
              return 1
       If v<=key[t] then
              return rank(left[t],v)
       Else
              return s[left[t]]+1+rank(right[t],v)





6 other

What's that does not say, are interested can look at the original paper.
The conclusion is:

The height of the 1.SBT O(logn)

The amortized running time is 2.Maintain: O(1)



A solution to the K element with the SBT example of the tree
Data structure and algorithm experiment 10.1 Oracle (4) method
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Abby at December 03, 2013 - 4:46 PM