# CSC301: Week 4: Balanced Search Trees (3.3)

 Contents [0/2]

 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.

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