Transcript relaxed balancing

Relaxed Balancing
Advanced Algorithms & Data Structures
Lecture Theme 09
Prof. Dr. Th. Ottmann
Summer Semester 2006
Example: Balanced search tree
10
6
15
2
9
2
5
5
7
6
7
11
10
9
11
23
15
20
30
20 23
Problem:
Updates come in sudden bursts (Example: Recording ink-traces from pen input)
Not enough time to serialize insertions and rebalancing transformations
Solution:
Relaxed balancing: Carry out updates and rebalancing transformations
concurrently!
2
Standard Balancing
Update operations and restructurings are carried out strictly sequentially.
Next search operation can be performed only when all restructurings (pointer
changes) have been completed.
3
1
2

1
2
3
3
Stratified search trees
…..
… …
…
…
..
..
4
Stratified search trees
•
A stratified search tree with n leaves has height at most log2 n.
•
Stratified search trees may be considered as a version of 2-3-4-trees (B-tress of
order 4)
5
Example
6
Example
7
Insertion
…..
…
…
…
…..
..
..
x p
…
Insert the new key among the leaves at the expected position
and deposit a „push-up-request“
8
Iterative sequence of insertions
9
Handling of push-up-requests (1)
•
A push-up-request either leads to a local structural change and halt, which can be
carried out in time O(1) (Case 1)
•
or (exclusively) to a recursive shift of the push-up-requests to the next higher
stratum without any structural change (Case 2)
Case 1 [There is still room on the next higher stratum]
3
1
1
2
1
3
4
1
23
4
2 3
2
3
1
2
4
1
23
4
10
Handling of push-up-requests (2)
Case 2 [Next higher stratum is full]
1
4
2
3
5
1
4
2
5
3
Append a new apex, if node is pushed over topmost stratum boarder
11
Deletion
…
…
…..
…
Locate x among the leaves.
Deposit a removal request at x.
Handle removal request.
…
..
..
…
…
12
Handling removal requests
Case 1 [Enough nodes at bottommost stratum]
Case 2 [Bottommost stratum too sparse]
Deposit „pull-down-request“
p
q
q
13
Handling of pull-down-requests (1)
Case1 [There are enough nodes on next higher stratum]
Finite structural change and
Halt!
p 1 2 3
p1 23 4
p 1 23 4
p12 3
1 2
1 2
p3 4
p 3 4
14
Handling of pull-down-requests (2)
Case 2 [Not enough nodes on next higher stratum]
q
q
p
p
Recursively shift pull-down-request to next higher stratum,
but no structural change!
15
Z-stratified search trees: Observations
Insertions, deletions, and rebalancing-transformations (removal of
arbitrarily interleaved.
,
) can be
The amortized restructuring costs per insertion or deletion are constant.
The generation history of a current version may be partially reconstructed (Sequence
of insertions and deletions are partially visible)
But:
•
Update operations are always applied to the current version
•
Z-stratified search trees are not persistent
16
Example of a randomised structure
Z-stratified search tree
…..
…
…
…
…..
..
..
On each stratum, randomly
choose the distribution of
trees from Z.
…
Insertion?
Deletion?
17