Augmenting Data Structures
CSC263 Week 5 Lecture 1
Augmented data structure = existing data structure
modified to store additional information and/or
perform additional operations
1. Choose data structure to augment
2. Determine the additional information
3. Check that additional information can be maintained during
each original operation
4. Implement new operations
Example: Ordered Sets
{144, 20, 100, 30, 17, 150, 55}
Rank: position within an ordered list — typically from lowest to highest
RANK(k): return rank of key k
SELECT(r): return the key with rank r
also support INSERT, DELETE and SEARCH
Zoom Chat
Approach 1: AVL tree without modificationChalk Talk
Queries:
Q: What will be the time for the new queries?
A:
Q: Will the other operations (SEARCH/INSERT/DELETE) take any longer?
A:
Problem: Query time. Can we do better?
Approach 2Chalk Talk
Augment AVL tree so each node has an additional field rank[x] that stores
its rank in the tree.
Approach 2: AVL storing rank and keyChalk Talk
Q: What will be the time for the new queries?
A:
Q: Will the other operations (SEARCH/INSERT/DELETE) take any longer?
A:
Problem: Query time. Can we do better?
Approach 3: store subtree sizeChalk Talk
Augment an AVL tree so that each node n has an additional field n.size()
that stores the number of keys in the subtree rooted at n (including n itself)
Zoom chat
Zoom chat
Approach 3: store subtree sizeChalk Talk
Q: How do we quickly find the rank of the root of the tree?
A:
Q: How do we quickly find the local (i.e. relative) rank of a node m
in the tree rooted at m?
A:
Zoom chat Identify the Local (Relative) Rank
Worksheet Worksheet Questions 1 & 2: implement SELECT
Worksheet Worksheet Questions 1 & 2
SELECT(T, k):
#
local_rank =
if local_rank == k:
if k < local_rank: else: Implement RANKChalk Talk Idea – Perform SEARCH on k and keep track of the current rank. Each time you go down a level by making a right turn, add the size of the subtrees to the left that you skipped. This is the local rank of the parent p you just left in the subtree rooted at p. Keep track of accumulating ranks. Worksheet Worksheet Questions 3 & 4 RANK Chalk Talk Q: How do we calculate the local rank of a node m in the tree rooted at m? A: Q: When we recurse on the left subtree what do we add? A: Q: When we recurse on the right subtree what do we add? A: Q: When we find x, how do we determine its true rank? A: RANK(T, k): return TREE-RANK(T.root, k, 0) TREE-RANK(root, k, current_rank): if root is NIL: # k not in S pass # determine my local_rank in the tree rooted at root if root.left == null: local_rank = 1 else: local_rank = _____________________________________ if k < root.item.key: # moving left so don't deduct anything return TREE-RANK(______________________________________________) else if k > root.item.key:
# moving right so add for items skipped
return TREE-RANK(_______________________________________________)
else: # x.key == root.item.key
# since we have found the item return our accumulated current rank
return _______________________________________
Chalk Talk
Q: Time for the new queries?
A:
Q: What about updates of new information in old operations?
Chalk Talk
Things to take away
Augmenting an AVL tree with size of subtree rooted at m, allowed us to
efficiently implement RANK and SELECT.
General strategy:
• Use known data-structure with extra information
• Extra information must be maintained on original operations
Final Reminders