Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Exam 7, Questions 12 and 13
#1
Can someone walk me through the rotations for number 12? I got 3 as the number of rotations, which is incorrect, but I don't understand how you would get 6 rotations from it.

Number 13 seems like it's a formula that needs to be memorized, what is the formula?
Reply
#2
#12

insert 7
   7
   ------------
   x is 7 (root)
insert 0
     7
    /
   0
   ------------
   x is 0 (case 2), x is 7 (root)
insert 1
     7                 7                  1
    /                 /                  / \
   0     rotate      1     rotate       0   7
    \               /
     1             0
   ------------
   x is 1 (case 2), x is 0 (case 3)
insert 5
     1
    / \
   0   7
      /
     5
   ------------
   x is 5 (case 2), x is 7 (case 2), x is 7 (root)
insert 6
     1                1                1
    / \              / \              / \
   0   7   rotate   0   7   rotate   0   6
      /                /                / \
     5                6                5   7
      \              /
       6            5
   ------------
   x is 6 (case 2, x is 5 (case 3
insert 2
     1                1                5
    / \              / \              / \
   0   6   rotate   0   5   rotate   1   6
      / \              / \          / \   \
     5   7            2   6        0   2   7
    /                      \
   2                        7
   ------------
   x is 2 (case 2), x is 5 (case 2), x is 6 (case 3)

#13

A linear tree would yield the most unbalanced tree and thus a tree with the most unbalanced factors. If it were a rightward descending tree, the leaf node would have a zero balance factor, it's parent -1, and the rest -2 and greater as you go up the tree.
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)