L-ET4148-50C-DB LSI, L-ET4148-50C-DB Datasheet - Page 275

• Manufacturer Part Number: L-ET4148-50C-DB
• Manufacturer: LSI

Specifications of L-ET4148-50C-DB

• Lead Free Status / RoHS Status: Supplier Unconfirmed

Preliminary Data Sheet
April 2006
Agere Systems Inc.
Appendix B: Configuration
Bridging
Since it is only permissible to swap occupied leaf nodes with empty leaf nodes, it is easy to see how swapping two
leaf nodes that share a common immediate ancestor would be quite simple.
For example, presume that node 4.0 is empty and 4.1 contains a valid key, say 327. The first step is to copy the
key in 4.1 to node 4.0. Since 3.0 hasn’t been updated yet, its current value of, say 320, continues to direct
searches looking for 327 to node 4.1. The search could, however, now obtain the same results by branching to 4.0.
Therefore, it is safe to update node 3.0 to, say 330, so that search arguments of 327 result in a branch to 4.0. At
this point, node 4.1 may be marked as invalid.
The updated structure is shown in the following figure.
Continuing with the example, let’s presume that we now want to swap nodes 4.1 and 4.2. Since node 4.1 is empty,
the contents of node 4.2 may be freely copied into node 4.1. Currently, a search argument value of 350 causes a
branch to the right at node 2.0. By depositing a value greater than 350, say 360, into node 2.0, future searches for
350 branch left at node 2.0 and then branch right at node 3.0. Node 4.2 may then be marked as invalid.
The binary tree examples presented above may be extended to 4-ary trees by bearing in mind that each node con-
tains three keys so as to provide for a 4-way branch. This means that node n.0 depends on the first key in the par-
ent node; node n.1 depends on the first and second key; node n.2 on the second and third key; while node n.3
depends on just the third key. Therefore, when nodes are being updated, it is important that all of the keys that are
associated with a branch in their direction be properly updated as well.
SEARCH ARGUMENTS LESS THAN OR EQUAL
TO KEYS CAUSE BRANCHES TO LEFT
4.0
(continued)
327
360
3.0
330
4.1
2.0
340
4.2
COMPARE SEARCH ARGUMENT TO ALL KEYS, THEN...
IF LESS THAN ALL KEYS, BRANCH TO (N+1).0
IF GREATER THAN ONE KEY, BRANCH TO (N+1).1
IF GREATER THAN TWO KEYS, BRANCH TO (N+1).2
IF GREATER THAN ALL KEYS, BRANCH TO (N+1).3
350
3.1
371
4.3
1.0
390
Figure 291. Updating a Binary Tree Structure (Step 2)
523
4.4
Single-Chip 48 x 1 Gbit/s + 2 x 10 Gbits/s Layer 2+ Ethernet Switch
3.2
Figure 292. Updating a 4-ary Tree Structure
4.5
2.1
(continued)
Agere Systems - Proprietary
4.6
3.3
4.7
0.0
784
4.8
3.4
4.9
2.2
4.10
SEARCH ARGUMENTS GREATER THAN KEYS
CAUSE BRANCHES TO RIGHT
3.5
4.11
1.1
4.12
204
1.0
3.6
220, 273, 434
4.13
257
1.1
2.3
0.0
4.14
341
1.2
3.7
4.15
477
1.3
ET4148-50
275