CSC301: Week 4: Balanced Search Trees (3.3)

 Contents [0/2]

 Homework [1/2] Homework grading [2/2]

(Click here for one slide per page)

 Homework [1/2]

• Read Algorithms 3.3 on balanced search trees.

• Complete the class `algs32.KdTree`. You can see instructions for a similar assignment here.

Hand in `KdTree.java` on d2l.

Do not rename or otherwise change any of the interfaces. I will grade it using the `Point2D` and `RectHV` classes that you are given.

```You should do the following problems on paper.
The problems are all quite easy, and will give you practice
with balanced trees.

You will hand in your answers in class or online.
If you hand in online, you must submit a word, pdf or text file.
You can write out your answers on paper and hand in a scan.
If you hand in a text file, be sure to used a fixed-width font like Courier.

I will grade two of these problems, chosen at random.

2-3 Trees:

3.3.1
3.3.2
3.3.3
3.3.5 --- structurally different means that they are different even
if all you ignore the values (take all values to be equal)
and you also ignore the order of the children

Red-Black Trees:

3.3.9
3.3.10
3.3.11
3.3.14
3.3.15
```

```3.3.1

AES =>  E
/ \
A   S

E         E S
/ \   =>  / | \
A  QSY    A  Q  Y

E S         E S U             S
/ | \   =>  / | | \   =>    /     \
A  Q TUY    A  Q T  Y       E       U
/ \     / \
A   Q   T   Y

S                   S
/     \             /     \
E       U    =>    E O       U
/ \     / \        / | \     / \
A  IOQ  T   Y      A  I  Q   T   Y

S
/     \
E O       U
/ | \     / \
A  IN Q   T   Y

===========================================================
3.3.2

LPY =>  P
/ \
L   Y

P          L P
/ \    =>  / | \
HLM  XY     H  M  XY

L P         L P X             P
/ | \   =>  / | | \   =>    /     \
CH M RXY    CH M R  Y       L       X
/ \     / \
CH  M   R   Y

P                   P
/     \             /     \
L       X    =>    C L       X
/ \     / \        / | \     / \
ACH  M   R   Y      A  H  M   R   Y

P
/     \
C L       X
/ | \     / \
A EH  M   RS  Y

===========================================================
3.3.3

Tree is:

E R
/  |  \
AC  HM  SX

Here's one class of solution:

Insert order:
+ first three inserted must include one of E,R and one from a leaf on either side.
+ next two include other of E,R + one from the leaf not included before.
+ the three remaining, which are from three different leaves

These are

AEH, RX
AEX, HR
ARX, EH
HRX, AE

where order within the groups doesn't matter
A could be C
H could be M
X could be S

But it's also possible:

AER, (C)HX
ERX, (S)AH

===========================================================
3.3.5

1:
*

2:
* *

3:
*
/   \
*     *

4:
*
/   \
*    **

5a:
*
/   \
* *   **

5b:
* *
/  |  \
*    *   *

6:
* *
/  |  \
*    *   **

7a (add to 3-node of 6):
*
/     \
*       *
/ \     / \
*   *   *   *

7b (add to 2-node of 6):
* *
/  |  \
**   *   **

8a (add to 2-node of 7a or 3-node of 7b):
*
/     \
*       *
/ \     / \
*   *   *   **

8b (add to 2-node of 7b):
* *
/  |  \
**   **  **

9a (add to 2-node of 8a or 3-node of 8b)
*
/     \
*       *
/ \     / \
*   *  **   **

9b (add to 2-node of 8a or 3-node of 8b)
*
/     \
*       *
/ \     / \
*   **  *   **

9c (add to 3-node of 8a)
*
/     \
*      * *
/ \    / | \
*   *  *  *  *

10a (add to 2-node of 9a or 9b)
*
/     \
*       *
/ \     / \
*   ** **   **

10b (add to 3-node of 9a or 2-node of 9c)
*
/     \
*      * *
/ \    / | \
*   *  *  *  **

10c (add to 3-node of 9b or 2-node of 9c)
*
/     \
*      * *
/ \    / | \
*   ** *  *  *

===========================================================
3.3.9

i)   no - not balanced
ii)  no - not balanced
iii) yes
iv)  yes

===========================================================
3.3.10

S                       S
/     \                 /     \
E O       U    ==        O       U
/ | \     / \           // \     / \
A  IN Q   T   Y          E   Q   T   Y
/ \
A   N
//
I

===========================================================
3.3.11

P                        P
/     \                 /       \
C L       X    ==        L         X
/ | \     / \           // \       / \
A EH  M   RS  Y          C   M     S   Y
/ \      //
A   H     R
//
E

===========================================================
3.3.14

A          B
\\  =>  //
B      A

B          B
// \\  =>   / \
A   C      A   C

B            B
/ \          / \
A   C   ==>  A   D
\\        //
D        C

B              B             D
/ \            / \\         // \
A   D    ==>   A   D   ==>   B   E
// \\           / \       / \
C   E          C   E     A   C

D               D
// \          //     \
B   E   ==>   B       F
/ \   \\      / \    //
A   C   F     A   C   E

D                   D                   D
//     \            //     \\            /     \
B       F   ==>     B       F   ==>     B       F
/ \    // \\        / \     / \         / \     / \
A   C   E   G       A   C   E   G       A   C   E   G

D                      D
/     \                /     \
B       F              B       F
/ \     / \     ==>    / \     / \
A   C   E   G          A   C   E   H
\\                  //
H                 G

D                    D                    D
/     \              /     \             /       \
B       F            B       F           B         H
/ \     / \    ==>   / \     / \\   ==>  / \      // \
A   C   E   H        A   C   E   H       A   C     F   I
// \\                 / \               / \
G   I                G   I             E   G

D                     D
/       \             /       \
B         H           B          H
/ \      // \    ==>  / \      //   \
A   C     F   I       A   C     F     J
/ \   \\              / \  //
E   G   J             E   G  I

D                        D                        D                       H
/       \                /       \                /       \\              //      \
B          H             B          H             B          H             D        J
/ \      //   \    ==>   / \      //   \\   ==>   / \       /   \   ==>   /   \     / \
A   C     F     J        A   C     F     J        A   C     F     J       B     F   I   K
/ \  // \\               / \   / \                / \   / \     / \   / \
E   G  I  K              E   G  I  K              E   G  I  K    A  C  E  G

On 2-3 threes:

ABC  =>   B
/ \
A   C

B         B D
/ \   =>  / | \
A  CDE    A  C  E

B D           B D F             D
/ | \    =>   / | | \  =>     /     \
A  C EFG      A  C E  G       B       F
/ \     / \
A   C   E   G

D                   D
/     \             /     \
B       F    =>     B       F H
/ \     / \         / \     / | \
A   C   E  GHI      A   C   E  G  I

D                    D                      D H
/     \              /     \              /     |     \
B       F H    =>    B       F H J   =>   B      F      J
/ \     / | \        / \     / | | \      / \    / \    / \
A   C   E  G IJK     A   C   E  G I  K    A   C  E   G  I   K

3-nodes pile up on the right in intermediate states.
At most one red link from root to leaf.

===========================================================
3.3.15
On 2-3 threes:

IJK  =>   J
/ \
I   K

J         H J
/ \   =>  / | \
GHI  K     G  I  K

H J           F H J             H
/ | \    =>   / | | \  =>     /     \
EFG I  K       E  G I  K       F       J
/ \     / \
E   G   I   K

H                  H
/     \           /       \
F       J   =>    D F       J
/ \     / \       / | \     / \
CDE  G   I   K     C  E  G   I   K

H                     H                      D H
/       \             /       \              /    |     \
D F       J   =>     B D F       J   =>     B      F       J
/ | \     / \        / | | \     / \        / \    / \     / \
ABC E  G   I   K      A  C E  G   I   K      A   C  E   G   I   K

3-nodes pile up on the left in intermediate states.
All red links on path from root to least node.

```

Revised: 2008/03/17 13:01