CODEWITHSUNDEEP
algorithmdata-structurestreebinary-search-tree
ojas
ojas

Reputation: 2210

How Digital search trees Work?

I have tried many online sources but i am unable to understand how digital binary search tree works.Below Link is the example for your reference (LINK: http://cseweb.ucsd.edu/~kube/cls/100/Lectures/lec15/lec15-10.html)

Is anybody construct a tree using these values and tell in detail that how it works?

A   00001
S   10011
E   00101
R   10010
C   00011
H   10100

Upvotes: 2

Views: 2032

Answers (2)

Vanathi Andiran
Vanathi Andiran

Reputation: 11

The DST works like by checking the bit level by level. Checks the starting of the bit if o then moves to left or else to right. At the same time it compares the bit position with the level.

For example:
Root is in the O level,

  • if the bit to be inserted is in the 1 st level then checks the 1st bit,
  • if 0 then inserts as a left or if it is 1 then insert in the right.

Similarly for the second level, checks the second bit to be inserted and works like this for the remaining levels.

In the given example;

First A (00001) is a root node, then S(10011) since 1 , move to the right and inserted.

The next is E(00101) , since 0 moves to left and inserted, next in the sequence is R(10010), since 1 move to the right , the bit in the second position is 0 so it is inserted as a left child of S.

In the sequence next is C(00011), 0 so moves to the left since 2nd bit is 0 insert in the left side, next is H(10100), since it starts with 1, moves to right, it has to be inserted as 3rd level so check the 3rd bit position as it is with 1, it is inserted in the right.

Hope this will clear your doubt. So the final DST looks like this [DST] [1]: https://i.sstatic.net/Iet4n.gif

Upvotes: 1

Codor
Codor

Reputation: 17605

The tree is constructed in such a way that the binary representations of the keys (A,S,E,R,C,H) can be used to locate them into the tree. In each searching step, the key is compared to the curren node (which is the root of the current search three). If the the key is not the root, the most significant bit of the key's binary representation is used to select the left subree (if the bit is 0) or the right subtree (if the bit is 1). This process is explained in more detail here.

In the example you provided, the key H (binary representation 10100) can be found as follows.

  1. In the first step, the root is node A. As A does not equal H, the bit 1 is used, indicating that the right subtree should be chosen. Consequently, we consider the node S and the bit string 0100 which results from the original binary representation by omission of the most significant bit.

  2. Since A does not equal H, we use the most significant bit, which is 0, indicating a choice of the left subtree. We consider the node R and the bit string 100.

  3. As R does not equal H, again we use the most significant bit, which is 1, which means that the right subtree is to be chosen. We consider the node H and the bit string 00.

  4. Since H equals H, we have found the desired key and the search terminates.

Upvotes: 2

Related Questions