| CSC403: HW Answers [2/2] | |
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.