HW3 Solutions Page
Return to
homework page.
4.19 Show result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an empty AVL tree.
Insert 2 Insert 1 Insert 4 Insert 5
(2) (2) (2) (2)
/ / \ / \
(1) (1) (4) (1) (4)
\
(5)
Insert 9 Insert 3 Insert 6 Insert 7
(2) (4) (4) (4)
/ \ / \ / \ / \
(1) (5) (2) (5) (2) (6) (2) (6)
/ \ / \ \ / \ / \ / \ / \
(4) (9) (1) (3) (9) (1)(3)(5)(9) (1)(3)(5) (9)
/
(7)
4.27 Show the result of accessing the keys 3, 9, 1, 5 in the following
splay tree:
____(10)______
__(4)__ (11)_
(2) (6) (12)
/ \ / \ \
(1) (3)(5) (8) (13)
/ \
(7) (9)
Access 3
Step 1
____(10)______
__(3)__ (11)_
(2) (4) (12)
/ \ \
(1) (6) (13)
/ \
(5) (8)
/ \
(7) (9)
Step 2
____(3)_____
__(2) _(10)_
(1) (4) (11)
\ \
(6) (12)
/ \ \
(5) (8) (13)
/ \
(7) (9)
Access 9
Step 1
____(3)_____
__(2) _(10)_
(1) (4) (11)
\ \
(9) (12)
/ \
(8) (13)
/
(6)
/ \
(5) (7)
Step 2
____(3)_____
__(2) _(9)__
(1) (4) (10)
\ \
(8) (11)
/ \
(6) (12)
/ \ \
(5) (7) (13)
Step 3
____(9)_____
__(3)__ (10)__
(2) (4) (11)
/ \ \
(1) (8) (12)
/ \
(6) (13)
/ \
(5) (7)
Access 1
Step 1
____(9)_____
(1)__ (10)__
(2) (11)
\ \
(3) (12)
\ \
(4) (13)
\
(8)
/
(6)
/ \
(5) (7)
Step 2
(1)_____
_(9)___
(2) (11)
\ \
(3) (12)
\ \
(4) (13)
\
(8)
/
(6)
/ \
(5) (7)
Access 5
Step 1
(1)_____
_(9)___
(2) (11)
\ \
(3) (12)
\ \
(4) (13)
\
(5)
\
(6)
\
(8)
/
(7)
Step 2
(1)_____
_(9)___
(2) (11)
\ \
(5) (12)
/ \ \
(4) (6) (13)
/ \
(3) (8)
/
(7)
Step 3
(1)_____
_(5)___
(2) (9)
\ / \
(4) (6) (11)
/ \ \
(3) (8) (12)
/ \
(7) (13)
Step 4
_(5)___
(1) (9)
\ / \
(2) (6) (11)
\ \ \
(4) (8) (12)
/ / \
(3) (7) (13)
4.28 Delete 6 from the splay tree that resulted from the previous exercise.
Step 1. Rotate 6 to root.
_(6)___
(5) (9)
/ / \
(1) (8) (11)
\ / \
(2) (7) (12)
\ \
(4) (13)
/
(3)
Step 2. Rotate largest in left subtree up to left subtree's root.
This is already true since 5 is largest in left subtree. Then
make right subtree the right subtree of this new left subtree
and delete old root.
___(5)___
(1) (9)
\ / \
(2) (8) (11)
\ / \
(4)(7) (12)
/ \
(3) (13)
4.43
A B*-tree of order M is a B-tree in which the interior node has between 2M/3
and M children. Describe a method to perform insertion into a B*-tree.
Aside: The point of B* trees is that since each node is at least two-thirds
full rather than half full as in the case of B-trees, the height
of a B*-tree will be typically be less than that of a B-tree with
the same number of things stored in it. Thus, fewer disk accesses
will be needed to access a node.
According to the definition in the statement of the problem, B*-tree
satisfies the conditions 1-5 on page 141 on the book except that condition (4)
has \lceil M/2 \rceil replaced with 2M/3. As in the book, we relax the
conditions for the first L insertions. Since condition (5) is unchanged
we will handle splittings of leaf nodes in the case of insertion as before.
Suppose now as a result of an insertion some internal node i now has M+1
keys. By condition (3) or (4), i is guaranteed to have at least one adjacent
sibling. Let s be the adjacent sibling with the smaller keys. Since before
the insertion the tree was a B*-tree s has at least 2M/3 elements. If the
total number of elements in i and s is <= 2M, we put the first half of the
elements in the node with the smaller keys and the remaining half of the
elements in the other node. Without loss of generality, suppose this other node
is i. We then change the key that points to i in the parent of i and s to be
smallest key in the new subtree under i. If the total number of elements in i
and s is 2M+1 we add a new node j off the parent of i and s right after
whichever of i and s has the larger elements. We then split the 2M keys and
their links into three groups of 2M/3 keys and their links. We put the smallest
2M/3 keys and links in the smallest node of i,s, the next 2M/3 keys and links
in the larger of i,s, and the last 2M/3 keys and links in j. We update the
keys associated with s,i,j in the parents node of these nodes appropriately.
If this parent node now has M+1 keys we do the same procedure as just described
for node i to it.
5.19
Show the results of inserting 10111101, 00000010, 10011011, 10111110,
01111111, 01010001, 10010110, 00001011, 11001111, 10011110, 11011011,
00101011, 01100001, 11110000, 01101111 into an empty extendible hash
structure with M=4.
I will use [ ] to denote the root node.
Step 1 Step2 Step 3 Step 4 Step 5
[ ] [ ] [ ] [ ] [ 0 | 1 ]
| | | | / \
10111101 00000010 00000010 00000010 00000010 10011011
10111101 10011011 10011011 01111111 10111101
10111101 10111101 10111110
10111110
Step 6 Step 7 Step 8
[ 0 | 1 ] [ 0 | 1 ] [ 0 | 1 ]
/ \ / \ / \
00000010 10011011 00000010 10010110 00000010 10010110
01010001 10111101 01010001 10011011 00001011 10011011
01111111 10111110 01111111 10111101 01010001 10111101
10111110 01111111 10111110
Step 9
[ 00 | 01 | 10 | 11 ]
\ / / \
00000010 10010110 11001111
00001011 10011011
01010001 10111101
01111111 10111110
Step 10
[ 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 ]
\____ | _/_______/ / | \ /
00000010 10010110 10111101 11001111
00001011 10011011 10111110
01010001 10011110
01111111
Step 11
[ 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 ]
\____ | _/_______/ / | \ /
00000010 10010110 10111101 11001111
00001011 10011011 10111110 11011011
01010001 10011110
01111111
Step 12
[ 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 ]
\ / \ / / | \ /
00000010 01010001 10010110 10111101 11001111
00001011 01111111 10011011 10111110 11011011
00101011 10011110
Step 13
[ 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 ]
\ / \ / / | \ /
00000010 01010001 10010110 10111101 11001111
00001011 01100001 10011011 10111110 11011011
00101011 01111111 10011110
Step 14
[ 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 ]
\ / \ / / | \ /
00000010 01010001 10010110 10111101 11001111
00001011 01100001 10011011 10111110 11011011
00101011 01111111 10011110 11110000
Step 15
[ 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 ]
\ / \ / / | \ /
00000010 01010001 10010110 10111101 11001111
00001011 01100001 10011011 10111110 11011011
00101011 01101111 10011110 11110000
01111111
//cs146sec6hw3file1.java - an application to draw AVL trees
import java.awt.*; // for drawing
import java.awt.event.*; // for window closing
import java.awt.geom.*; // for Rectangle
import javax.swing.*; // for JFrame
/**
This application draws randomly created AVL trees into a
JFrame. It is run from the command line with a line like
java cs146sec6hw3file1 xSize ySize num range
It would then create a xSize x ySize JFrame. The application
then generates num many random numbers less than range and
inserts them into an AVL tree which it then graphically draws.
@author Chris Pollett
@version 1.0
*/
public class cs146sec6hw3file1 extends JFrame
{
/**
The constructor creates a new AvlTree and insert into it
numberOfRandoms meany random numbers less than rangeOfNumbers.
@param numberOfRandoms - the number of random numbers to generate.
@param rangeOfRandoms - the max value for the random numbers
*/
public cs146sec6hw3file1( int numberOfRandoms, int rangeOfRandoms)
{
super("AVL Drawer");
avlTree = new AvlTree();
int random;
for(int i = 0; i < numberOfRandoms; i++)
{
random = (int)(Math.random()*rangeOfRandoms);
avlTree.insert(new Integer(random));
}
}
/**
Called whenever our frame needs to be painted.
This method clear the screen and gets the size of the
rectangle that tree must draw into. Then draws the AvlTree.
@param g - graphics context for frame
*/
public void paint(Graphics g)
{
Rectangle screenBounds = getContentPane().getBounds();
screenBounds.y += screenBounds.height/SCALING;
screenBounds.height -= screenBounds.height/SCALING;
g.clearRect(screenBounds.x, screenBounds.y,
screenBounds.width, screenBounds.height);
g.setColor(Color.blue);
avlTree.drawTree(g, screenBounds);
}
// Main entry point
public static void main(String[] args)
{
if( args.length < 4 )
{
System.err.println("You need four command line arguments:");
System.err.println("sizeX sizeY number_of_randoms randoms_range");
System.exit(1);
}
cs146sec6hw3file1 app = new cs146sec6hw3file1(Integer.parseInt(args[2]),
Integer.parseInt(args[3]));
app.setSize(Integer.parseInt(args[0]), Integer.parseInt(args[1]));
app.setBackground(Color.black);
app.addWindowListener( new WindowAdapter() //anonymous inner class
{
public void windowClosing( WindowEvent e)
{
System.exit(0);
}
}
);
app.show();
}
AvlTree avlTree;
static final int SCALING = 8;
} //end cs146sec6hw2file1.java
/**
What follows is essentially the code from the book for the
AvlTree structure. We have deleted some methods and made class
non-public so everything fits into one file. We have added
to the class a drawTree method that can be used to draw the
AvlTree to a Graphics object. Have left methods as public
that would be public if had multiple files. Left their javadoc
comments as well.
*/
class AvlTree
{
/**
Construct the tree.
*/
public AvlTree( )
{
root = null;
}
/**
Insert into the tree; duplicates are ignored.
@param x the item to insert.
*/
public void insert( Comparable x )
{
root = insert( x, root );
}
/**
Draws the current AvlTree to the graphics context
within the specified rectangular bounds.
@param g - the graphics context
@param bounds - the rectangular bounds.
*/
public void drawTree(Graphics g, Rectangle bounds)
{
int screenHeightOffset = bounds.height/root.height;
drawTree(g,root,bounds,screenHeightOffset);
}
/*
Draws tree rooted at t to graphics context g within the
rectangular bounds and with each level of tree offset
many pixels below previous.
*/
private void drawTree(Graphics g, AvlNode t, Rectangle bounds, int offset)
{
int treeY = bounds.y;
int fontHeight = g.getFontMetrics().getHeight();
int subtreeY = treeY + offset;
int subtreeHeight = bounds.height - offset;
int subtreeWidth = bounds.width/2;
int leftTreeX = bounds.x;
int rightTreeX = leftTreeX + subtreeWidth;
// draw in post-order
if(t.left != null) //draw left tree and line from root
{
drawTree(g, t.left, new Rectangle(leftTreeX, subtreeY,
subtreeWidth, subtreeHeight), offset);
g.drawLine(rightTreeX, treeY,
leftTreeX + subtreeWidth/2, subtreeY-fontHeight);
}
if(t.right != null) //draw right tree and line from root
{
drawTree(g, t.right, new Rectangle(rightTreeX, subtreeY,
subtreeWidth, subtreeHeight), offset);
g.drawLine(rightTreeX, treeY,
rightTreeX + subtreeWidth/2, subtreeY-fontHeight);
}
//draw root
g.drawString(t.element.toString(), rightTreeX, treeY);
}
private AvlNode insert( Comparable x, AvlNode t )
{
if( t == null )
t = new AvlNode( x, null, null );
else if( x.compareTo( t.element ) < 0 )
{
t.left = insert( x, t.left );
if( height( t.left ) - height( t.right ) == 2 )
if( x.compareTo( t.left.element ) < 0 )
t = rotateWithLeftChild( t );
else
t = doubleWithLeftChild( t );
}
else if( x.compareTo( t.element ) > 0 )
{
t.right = insert( x, t.right );
if( height( t.right ) - height( t.left ) == 2 )
if( x.compareTo( t.right.element ) > 0 )
t = rotateWithRightChild( t );
else
t = doubleWithRightChild( t );
}
else
; // Duplicate; do nothing
t.height = max( height( t.left ), height( t.right ) ) + 1;
return t;
}
/*
Return the height of node t, or -1, if null.
*/
private static int height( AvlNode t )
{
return t == null ? -1 : t.height;
}
/*
Return maximum of lhs and rhs.
*/
private static int max( int lhs, int rhs )
{
return lhs > rhs ? lhs : rhs;
}
/*
Rotate binary tree node with left child.
For AVL trees, this is a single rotation for case 1.
Update heights, then return new root.
*/
private static AvlNode rotateWithLeftChild( AvlNode k2 )
{
AvlNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max( height( k2.left ), height( k2.right ) ) + 1;
k1.height = max( height( k1.left ), k2.height ) + 1;
return k1;
}
/*
Rotate binary tree node with right child.
For AVL trees, this is a single rotation for case 4.
Update heights, then return new root.
*/
private static AvlNode rotateWithRightChild( AvlNode k1 )
{
AvlNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = max( height( k1.left ), height( k1.right ) ) + 1;
k2.height = max( height( k2.right ), k1.height ) + 1;
return k2;
}
/*
Double rotate binary tree node: first left child
with its right child; then node k3 with new left child.
For AVL trees, this is a double rotation for case 2.
Update heights, then return new root.
*/
private static AvlNode doubleWithLeftChild( AvlNode k3 )
{
k3.left = rotateWithRightChild( k3.left );
return rotateWithLeftChild( k3 );
}
/*
Double rotate binary tree node: first right child
with its left child; then node k1 with new right child.
For AVL trees, this is a double rotation for case 3.
Update heights, then return new root.
*/
private static AvlNode doubleWithRightChild( AvlNode k1 )
{
k1.right = rotateWithLeftChild( k1.right );
return rotateWithRightChild( k1 );
}
/* The tree root. */
private AvlNode root;
}
/*
This class encapsulates the nodes for the AvlTree class.
*/
class AvlNode
{
// Constructors
AvlNode( Comparable theElement )
{
this( theElement, null, null );
}
AvlNode( Comparable theElement, AvlNode lt, AvlNode rt )
{
element = theElement;
left = lt;
right = rt;
height = 0;
}
// Friendly data; accessible by other package routines
Comparable element; // The data in the node
AvlNode left; // Left child
AvlNode right; // Right child
int height; // Height
}