Answers to written HW#1

Updated: 4/21/98

Please note that when tree construction is called for, the answers are sometimes non-unique. The trees provided below are just one option.

Also, please note that I use brackets to denote nodes below. This causes some web browsers to barf on the tree diagrams below (namely, Lynx doesn't show any of the numbers). If you have this problem, view the page source to see the trees, or use another browser. I'll try to use better notation next time.

Self-Test Exercises:

What is the result of inserting 5,40,10,20,15,30 into an intially empty 2-3 tree?
The steps are:

```
	<5>
```
```
       <5 40>
```

	<10>
	/  \
       /    \
     <5>    <40>

	<10>
	/  \
       /    \
     <5>   <20 40>

	<10 20>
	/  |  \
       /   |   \
     <5>  <15> <40>

	<10 20>
	/  |  \
       /   |   \
     <5>  <15> <30 40>

- What is the result of deleting 10 from the last tree in #1?
  10's inorder successor is 15, so we swap them:
```
	<15 20>
	/  |  \
       /   |   \
     <5>  <10> <30 40>
```
  Then 10's node has no other items, so deleting 10 would leave an empty node behind. The rightmost sibling has 2 data items, though, so we redistribute:
```
	<15 30>
	/  |  \
       /   |   \
     <5>  <20> <40>
```
- What is the result of inserting 3 and 4 into the last tree from #1?
```
	<10>
	/  \
       /    \
     <4>   <20>
    / |    |  \
   /  |    |   \
 <3> <5>  <15> <30 40>
```

Repeat #1 for a 2-3-4 tree.

```
	<5>
```
```
      <5 40>
```
```
    <5 10 40>
```

	<10>
	/  \
       /    \
     <5>    <20 40>

	<10>
	/  \
       /    \
     <5>    <15 20 40>

	<10 20>
	/  |  \
       /   |   \
     <5>  <15> <30 40>

Insert 3 and 4 into the tree from the previous part.

	<10 20>
	/  |  \
       /   |   \
 <3 4 5>  <15> <30 40>

What red-black tree represents the 2-3-4 tree in 12-27a?
12-27a is:

	  <50>
        /    \
       /      \
      <30>     <70>
    /     \      |  \
   |       \     |   \
<10 15 20> <40> <60> <80 90>

The red-black tree for it is:

	  <50>
        /    \
       /      \
      <30>     <70>
    /     \      |  \
   |       \     |   \
  <15>    <40> <60>  <80>
  )  (                   (
 )    (                   (
<10>  <20>                <90>

(where the ('s and )'s are used to denote dashed, or "red" lines, and the slashes and pipes denote solid, or "black" lines).

If your application of the ADT table involves only retrieval what tree would provide for the most efficient table implementation?
If no insertions and deletions occur then there is no opportunity for a balanced binary tree to get out of whack, so it would be most efficient (all of the trees we've seen take O(log(n)) time in the number of nodes, but all but the first require some overhead storage and computations).
Why does a node in a red-black tree require less memory than a node in a 2-3-4 tree?
In a 2-3-4 tree, a lot of storage is wasted in non-existant children and data items (which *could* exist, but don't in the particular tree in question). In the red-black equivalent, storage is only allocated for data and children that *do* exist (one at a time), so this waste is not commited.

Exercises:

Execute the following instructions: Insert(10), Insert(100), Insert(30), Insert(80), Insert(50), Delete(10), Insert(60), Insert(70), Insert(40), Delete(80), Insert(90), Insert(20), Delete(30), Delete(70) on a table implemented via: BST, 2-3 tree, 2-3-4 tree, red-black tree, AVL tree.
We do these in order by type of tree:

Binary search tree:

 	    <100>
  	    /
	   /
	  <40>
         /   \
        /     \
       <20>    <50>
                 \
		  \
		  <60>
		    \
		     \
		     <90>

2-3 tree:

	<50 90>
       /   |  \
      /    |   \
 <20 40>  <60> <100>

2-3-4 tree:

	<50 90>
       /   |   \
      /    |    \
 <20 40>  <60>  <100>

Red-black tree:

	<50>
       /    (
      /      ( 
    <20>     <90>
      (      /  \
       (    /    \
      <40> <60>  <100>

AVL tree:

	<50>
       /   \
      /     \
    <40>    <90>
    /      /   \
   /      /     \
 <20>   <60>    <100>

What are the advantages of implementing the ADT table with a 2-3 tree instead of a binary search tree? Why do you not, in general, maintain a completely balanced binary search tree?
A 2-3 tree has the advantage that its balance does not get destroyed with each insertion or deletion, as happens in a completely balanced BST. Also, the fact that each node can hold more pieces of data means that restoring the balance once takes care of more than one "outstanding" order of business. (i.e., where a BST would get re-arranged twice, a 2-3 tree only needs to be done once, after the second "disturbance" appears).

Write a pseudo-code function that visits all items in a particular range in a 2-3 tree.

VisitRange(T, fromKey, toKey)
// Visits each item in T with key between fromKey and toKey
if (T's root is a leaf)
    if (fromKey<=T.ldata <=toKey) // visit T.ldata
    if (fromKey<=T.rdata <=toKey) // visit T.rdata
else    
    if (T has 2 items)
      if (fromKeyT.ldata))
         VisitRange(T.mChild, fromKey, toKey)
      if (fromKey<=T.rdata <=toKey) // visit T.rdata
      if (toKey>T.rdata)
         VisitRange(T.rChild, fromKey, toKey)
    else // T has 1 data item
      if (fromKeyT.ldata) 
         VisitRange(T.mChild, fromKey, toKey)

Assume that the tree in 12-5b is a 2-3-4 tree. Insert 39, 38, 37, 36, 35, 34, 33, 32 into it. What tree results?
The tree we start with is:

     	<50>
       /    \
      /      \
     <30>     <70 90>
    /   \       / |  \
   /     \     /  |   \
<10 20>  <40><60><80> <100>

The result is:

  	                   <37 50>
	      ____________/   |  \___________
             /                |              \
          <30 35>            <39>         <70 90>
      ____/  |   \_____      /  \         /  |  \
     /       |         \    /    \       /   |   \
<10 20> <32 33 34>    <36> <38>  <40>  <60> <80> <100>

Not assigned

Figure 12-33 is a red-black tree that represents the 2-3-4 tree in figure 12-20. Draw another such red-black tree.

		<50>
	       )   \________________
	      )	                    \
	     <37>		    <70>
	    /   \______             /  (
	   /           \           /    (
	  <35>        <39>       <60>	<90>
	 )   \        / \               /  \
	)     \      /   \             /    \
       <30>   <36> <38>  <40>        <80>  <100>
       /  \
      /    \
     <20>  <33>
    )      )  (
   )      )    (
   <10>  <32>  <34>

What 2-3-4 tree does the tree in 12-55 represent?

  	                <37 50>
	   ____________/   |   \______________
	  /                |                  \
      <30 35>             <39>            <70 85 90>
     /   |   \______       / \           /  |  |__  \____
    /    |          \     /   \         /   |     |      \
<10 20> <32 33 34> <36> <38> <40 45> <60 65><80> <87 89> <100>