- 3 The Radix Tree Data Structure Shown Below Stores The Bit Strings 0 1 01 010 100 And 1011 In Such A Way That Each Le 1 (147.82 KiB) Viewed 24 times
PLEASE ANSWER SUBQUESTIONS
*ANSWER TO
QUESTION 1:*
- 3 The Radix Tree Data Structure Shown Below Stores The Bit Strings 0 1 01 010 100 And 1011 In Such A Way That Each Le 2 (158.39 KiB) Viewed 24 times
3. The radix tree data structure shown below stores the bit strings 0,1,01,010, 100, and 1011 in such a way that each left branch represents a 0 and each right branch represents a 1. 0 X 1 1 1 91 X . / 010 100 X 1011 Nodes that do not have any stored bit strings will have a dummy value 'X' instead. To find whether a bit string exists in this radix tree, start from the root, and scanning the bits of the string left to right, take a left turn if the but is 0, and a right turn if the bit is 1. If a node can be reached using this sequence of turns, and it does not contain the dummy value 'X', then the bit string is found, else it is not found. 1. Given the following bit strings: 1011, 01, 0010, 1010, 011, 1000, 0101 Starting with an empty radix tree, build it up to store these strings, showing the radix tree after each bit string is inserted. (To insert a new string you may have to insert more than one new node in the tree built thus far.) 2. How many units of time did it take to build this tree? Treat taking a turn at an existing branch, and inserting a new branch as basic unit time operations. 3. How many units of time would it take to lexicographically sort the bit strings in this radix tree, after all the strings have been inserted? Use the same basic operations as in the previous
question. The output of the sort should be: 0010 01 0101 011 1000 1010 1011 (Lexicographic sort is like alphabetic sort, 0 precedes 1) 4. How many units of time would it take in the worst case to insert a new k-bit string into a radix tree? (ANY radix tree, not the specific one above.) 5. How many units of time would it take in the worst case to insert an arbitrary number of bit strings whose total length is n bits?
Step 0: empty radix tree Step 1: insert 1011 0 100 X X X 1011 Step 2: insert 01 0 01 x 100 1 X 1011 X 0010 Step 3: insert 0010 X 0 01 X 001 100 1011 X 0010 Step 4: insert 1010 0 01 001 100 1010 X 1 1011 Step 5: insert 011 X 0010 001 0 01 011 100 1010 X X X 1011 X 0010 Step 6: insert 1000 001 0 01 011 100 1000 X 1010 X X X 1011 X 0010 Step 7: insert 0101 0 001 X 01 011 0101 1000 100 1010 1 X 1011