Binary Tries 4y1s26

Binary Tries (continued) • split(k). • Similar to split algorithm for unbalanced binary search trees. • Construct S and B on way down the trie. • Follow with a backward cleanup over the constructed S and B.

Forward • Suppose you are at node x, which is at level j of the input trie.

x

a

b

• If bit j of k is 1, move to root of b and add

a

to level j of S and

to level j of B.

Forward x a

b

• If bit j of k is 0, move to root of a and add

to level j of B and b

to level j of S.

Forward Example S = null

a b

c d

e f

g

k = g.key = 101011

B = null

Forward Example S

a b

c d

e f

g

k = g.key = 101011

B

Forward Example S

B

a b

c d

e f

g

k = g.key = 101011

Forward Example S

B

a b c d

e f

g

k = g.key = 101011

Forward Example S

B

a b c d

e f

g

k = g.key = 101011

Forward Example S

B

a b c d f

g

e

k = g.key = 101011

Forward Example S

B

a b c d e k = g.key = 101011

f

Backward Cleanup • Retrace path from current nodes in S and B toward roots of respective tries. • Eliminate branch nodes that are roots of subtries that have fewer than 2 dictionary pairs.

Backward Cleanup Example S

B

a f is an element node.

b c d e f

Backward Cleanup Example S

B

a Now backup on B.

b c d e

f

Backward Cleanup Example S

B

a Now backup on B.

b c d e

f

Backward Cleanup Example S

B

a Now backup on B.

b c

Assume root of d is a branch node.

d e

f

Backward Cleanup Example S

B

a Complexity of split is O(height).

b c d e

f

Compressed Binary Tries • No branch node whose degree is 1. • Add a bit# field to each branch node. • bit# tells you which bit of the key to use to decide whether to move to the left or right subtrie.

Binary Trie 1 0

3 0 0001

1 0

0 1 0011

2

4

0 1000

1

0 4

1 1001

0

0 1100

bit# field shown in black outside branch node.

1 1101

Compressed Binary Trie 0

1 1

3 0 0001

2 1 0011

0 4

0 1000

1 4

1 1001

0 1100

bit# field shown in black outside branch node.

1 1101

Compressed Binary Trie 0

1 1

3 0 0001

2 1 0011

0 4

0 1000

#branch nodes = n – 1.

1 4

1 1001

0 1100

1 1101

Insert 0

1 1

3 0 0001

2 1 0011

0 4

0 1000

Insert 0010.

1 4

1 1001

0 1100

1 1101

Insert 0

1 1

3

2

0

1 4

0001 0

0010

1

0011

0 4

0 1000

Insert 0100.

1 4

1 1001

0 1100

1 1101

Insert 0

1

1

2

2

3

1

0

0100

0

1

4

0001 0 0010

1 0011

0 4 0

1000

1 4

1

1001

0

1

1100 1101

Delete 0

1

1

2

2

3

1

0

0100

0

1

4

0001 0 0010

1 0011

0

1

4 0

1000

4 1

1001

0 1100

Delete 0010.

1

1101

Delete 0

1 1 2

2 3 0 0001

1

0

0100 1 0011

Delete 1001.

0 4

0 1000

1 4

1 1001

0 1100

1 1101

Delete 0

1 1 2

2 3 0 0001

1

0

0100 1 0011

0 1000

1 4 0 1100

1 1101

Split(k) • Similar to splitting an uncompressed binary trie.

(S,m,B) • Insert m into B to get B’. • |S| <= 1 or |B’| = 1 handled as special cases as in the case of uncompressed tries. • When |S| > 1 and |B’| > 1, let Smax be the largest key in S and let B’min be the smallest key in B’. • Let d be the first bit that is different in Smax and B’min.

Cases To Consider bit#(S)

bit#(B’)

0

1

0

1

a

b

c

d

S • d < min{bit#(S), bit#(B’)} • d >= min{bit#(S), bit#(B’)}

 bit#(S) = bit#(B’)  bit#(S) < bit#(B’)

 bit#(S) > bit#(B’)

B’

d < min{bit#(S), bit#(B’)} Bit d of Smax must be 0.

d 0

1

S

B’

bit#(S) = bit#(B’) s

s

0

1

0

1

a

b

c

d

S

B’

• Not possible, because keys in b are larger than those in c.

• However, all keys in S are supposed to be smaller than those in B’.

bit#(S) < bit#(B’) s

s

b’

0

1

0

1

0

1

a

b

c

d

a

J(b,B’)

S

B’

bit#(S) > bit#(B’) s

b’

b’

0

1

0

1

0

1

a

b

c

d

J(S,c)

d

S

B’

Complexity is O(max{height(S), height(B)}).

Smax and B’min are found just once.

PATRICIA • Practical Algorithm To Retrieve Information Coded In Alphanumeric. • Compressed binary trie. • All nodes are of the same data type (binary tries use branch and element nodes).  Pointers to only one kind of node.  Simpler storage management.

Compressed Binary Trie To Patricia 0 3 0 000 1

1 1 2

1 001 1

0 4 0 100 0

1 100 1

1 4 0 110 0

1 110 1 Move each element into an ancestor or header node.

Compressed Binary Trie To Patricia 0

0001

1 0

3

1101 1 2

0011 0 1

1001 4 0

0

4

1000 1

1 1100

0

1