Digital Search Tree

13-Nov-14
DIGITAL SEARCH TREES
Definition
A digital search tree is a binary tree in
which each node contains one element.
The element-to-node assignment is
determined by the binary representation
of the element keys.
13-Nov-14
We number the bits in the binary

representation of a key from left to right
beginning at one.
Ex: bit one of 1000 is 1, and bits two ,
three , four are 0.
All keys in the left subtree of a node at
level I have bit i equal to zero whereas
those in the right subtree of nodes at
this level have bit i = 1.
Digital Search Tree

Assume fixed number of bits
Not empty =>
Root contains one dictionary pair (any pair)
All remaining pairs whose key begins with
a 0 are in the left subtree.
All remaining pairs whose key begins with
a 1 are in the right subtree.
Left and right subtrees are digital subtrees
on remaining bits.
13-Nov-14
This digital search tree contains

the keys
1000,0010,1001,0001,1100,0000
1000
0010
1001
0001
1100
0000
Example
Start with an empty digital search tree
and
insert a pair whose key is 0110
0110
13-Nov-14
Now , insert a pair whose key is 0010
0110
0010
Example
0110
0010
1001
13-Nov-14
Example
Now insert a pair whose key is 1011
0110
0010
0110
1001
0010
1001
1011
Example
0110
0110
0010
0010
1001
1011
0000
1001
1011
13-Nov-14
Search and Insert

The digital search tree functions to search
and insert are quite similar to the
corresponding functions for binary search
trees.
The essential difference is that the subtree
to move to is determined by a bit in the
search key rather than by the result of the
comparison of the search key and the key in
the current node.
Try to build the digital

search tree
A
S
E
R
C
H
I
N
G
X
M
P
00001
10011
00101
10010
00011
01000
01001
01110
00111
11000
01101
10000
13-Nov-14
Digital Search Tree

A
S
E
C
H
G I
Practical
When we dealing with very long keys,
the cost of a key comparison is high.
We can reduce the number of key
comparisons to one by using a related
structure called Patricia
We shall develop this structure in
three steps.
13-Nov-14
First, we introduce a structure called a

binary trie.
Then we transform binary tries into
compressed binary tries.
Finally, from compressed binary tries
we obtain Patricia.
Binary Tries
A binary trie is a binary tree that has two
kinds of nodes: branch nodes and element
nodes.
A branch node has the two data members
LeftChild and RightChild. It has no data
member.
An element node has the single data
member data.
Branch nodes are used to build a binary tree
search structure similar to that of a digital
search tree. This leads to element nodes
13-Nov-14
A six-element binary trie
1100
0010
0000
0001
1000
1001
Compressed binary trie

The binary trie contains branch nodes
whose degree is one. By adding
another data member, BitNumber , to
each branch node, we can eliminate all
degree-one branch nodes from the trie.
The BitNumber data member of a
branch node gives the bit number of
the key that is to be used at this node.
13-Nov-14
Binary trie with degreeone nodes eliminated

1
3
4
0010
0000
0001
1100
1000
1001
Patricia
Compressed binary tries may be
represented using nodes of a single
type. The new nodes, called
augmented branch nodes, are the
original branch nodes augmented by
the data member data. The resulting
structure is called Patricia and is
obtained from a compressed binary
trie in the following way:
10
13-Nov-14
(1)Replace each branch node by an

augmented branch node.
(2)Eliminate the element nodes.
(3)Store the data previously in the element node in the data
data members of the augmented branch nodes. Since every
nonempty compressed binary trie has one less branch node
than it has element nodes, it is necessary to add one
augmented branch node. This node is called the head node .
The remaining structure is the left subtree of the head node.
The head node has BitNumber equal to zero. Its right-child
data member is not used. The assignment of data to
augmented branch node is less than or equal to that in the
parent of the element node that contained this data .
(4)Replace the original pointers to element

nodes by pointers to the respective
augmented branch nodes.
Patricia
0
1100
1
0000
0010
1001
4
0001
1000
11
13-Nov-14
Patricia
typedef struct patricia_tree *patricia;
struct patricia_tree {
int bit_number;
element data;
patricia left_child, right_child;
};
patricia root;
Patricia Search
Patricia search(patricia t, unsigned k)
{
/*search the Patricia tree t; return the last node y encountered; if k =
y ->data.key, the key is in the tree */
Patricia p, y;
If (!t) return NULL; /* empty tree*/
y=t->left_child;
p=t;
while (y->bit_number > p->bit_number){
p=y;
y=(bit(k, y->bit_number)) ?
y->right_child : y->left_child;
}
return y;
}
12
13-Nov-14
PatriciaInsert
void insert (patricia *t, element x){
/* insert x into the Patricia tree *t */
patricia s, p, y, z;
int i;
if (!(*t)) { /* empty tree*/
*t = (patricia)malloc(sizeof(patricia_tree));
if (IS_FULL(*t)) {
fprintf(stderr, The memory is full\n) ;
exit(1);
}
(*t)->bit_number = 0
(*t)->data = x;
(*t)->left_child = *t;
}
y = search(*t,x.key);
if (x.key == y->data.key) {
fprintf(stderr, The key is in the tree. Insertion fails.\n);
exit(1);}
/* find the first bit where x.key and y->data.key differ*/

for(i = 1; bit (x.key,i) == bit(y->data.key,i); i++ );
/* search tree using the first i-1 bits*/
s = (*t)->left_child;
p = *t;
while (s->bit_number > p->bit_number && s->bit_number < 1){
p = s;
s = (bit(x.key,s->bit_number)) ?
s->right_child : s->left_child;}
/* add x as a child of p */
z = (patricia)malloc(sizeof(patricia_tree));
if (IS_FULL(z)) {
fprintf(stderr, The memory is full\n);
exit(1);
}
z->data = x;
z->bit_number = i;
z->left_child = (bit(x.key,i)) ? s: z;
z->right_child = (bit(x.key,i)) ? z : s;
if (s == p->left_child)
p->left_child = z;
else
p->right_child = z;
13
13-Nov-14
0
1000
1000
t
0
1
0010
1000
0010
4
(a)1000 inserted
(b)0010 inserted
1001
(c)1001 inserted
0
1000
1000
0010
2
1100
0010
0000
4
1001
(d)1100 inserted
2
1100
1001
(e)0000 inserted
14
13-Nov-14
0010
1000
2
0000
1100
4
0001
4
1001
(f)0001 inserted
THE END
15

Digital Search Tree

Uploaded by

Copyright:

Available Formats

Digital Search Tree

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Digital Search Tree

Uploaded by

Copyright:

Available Formats

13-Nov-14

DIGITAL SEARCH TREES

We number the bits in the binary

Digital Search Tree

This digital search tree contains

Now , insert a pair whose key is 0010

Search and Insert

Try to build the digital

Digital Search Tree

First, we introduce a structure called a

A six-element binary trie

Compressed binary trie

Binary trie with degreeone nodes eliminated

(1)Replace each branch node by an

(4)Replace the original pointers to element

/* find the first bit where x.key and y->data.key differ*/

You might also like