Question 1
a)
4− 3− 50
10
8+
11− 9+
100
15−
130
b)
18+
200 30
110
CSC263 – Assignment 3
Cristyn Howard Tuesday, Februrary 13, 2018
.
Question 2
8−
15+ 130 18+
200
9+ 10 50 100
a) Let each integer i ∈ S serve as the key for a node in an AVL tree. Each node x additionally stores:
– x.count : number of nodes in the subtree rooted at x whose keys are less than or equal to x.key (x included) |R|, where [i ∈ R ⊂ S] ↔ [(i ∈ x.subtree) ∧ (i.key ≤ x.key)]
– x.keysum : sum of keys of nodes in subtree rooted at x that are less than or equal to x.key (x included) i.key ∀i ∈ x.subtree ⊂ S | i.key ≤ x.key
Note that for a node z with no children, we have z.count = 1 and z.keysum = z.key. Here is an example, taken from question 1a:
10 count:1 ks:1
9+ 130 200 count:1 count:1 count:1 ks:9 ks : 13 ks:20
100 count : 1 ks:10
8+ count : 5 ks:21
4− count : 3
15− count : 5
ks:8 ks:58
3− 50 11− 18+
count:2 count:1 count:3
ks:4 ks:5 ks:30 ks:18
count:1
1
b) ADD(i)
1. create node x with key i, then insert x as in normal AVL tree (BST insert, rebalance)
– Whenever rebalancing means that a subtree y.subtree (i.e. subtree rooted at y) becomes the new left child of node z, z and all ancestor nodes of z with keys is greater than or equal to z.key must be amended so that: zOrAncestorOfZ.keysum+ = y.keysum,zOrAncestorOfZ.count+ = y.count
2. go up ancestor nodes of x in it’s final position until root is reached, and for each ancestor node whose key is greater than or equal to x.key, add x.key to the keysum of the ancestor and increment the ancestors count attribute by 1.
– ADD ∈ O(logn) because the number of constant time operations (adjusting counts and keysums of ancestors after rebalancing or adding node) is limited by the height of the tree, which for an AVL tree with n nodes is ⌊logn⌋.
AVERAGE(t)
1. find the node x in the AVL BST whose key is the largest integer in S that is less than or equal to t (return
0 if none in S < t)
2. start with x’s keysum and count
3. go up ancestor nodes until root is reached, and for each ancestor node whose key is less than or equal to x.key, add that ancestor’s keysum and count to the working total keysum and count
4. when root is reached, if count > 1 (i.e. if there is at least one node in T with key <= x.key) divide keysum by count and return the result as the average
- AVERAGE ∈ O(logn) because the number of constant time operations is limited by the number of nodes between x and the root of the tree, which for an AVL tree with n nodes is at most ⌊logn⌋.
Here is some psuedocode for AVERAGE:
2