Comment on page

Tree

Abstract Data Type (ADT)

A mathematical model for data types:
  • How to store data
  • What query to support? (lookup, findMin, findSum, …)
  • What update to support? (insertion, deletion, filter, multi_insert, delete_min, …)
  • Algorithms for the operations

Examples of ADT

  • FIFO Queue
  • Deque (double-ended queue)
  • Stack
  • Priority queue
  • Ordered set/map
  • Unordered set/map

Winning Tree

  • An implementation of priority queue
  • Easy to implement, same bound as binary heap
  • Can also be used as a static version of search tree

Similar concepts

  • Also Winner Tree, Tournament Tree
  • Segment Tree (w/o insert, delete operations).
  • Fenwick tree or binary indexed tree (only used to efficiently calculate prefix sums)

Use case (as priority queue)

  • Huffman coding: need extract_min and insertion
  • Dijkstra's algorithm and Prim's algorithm: extract_min and add/update

Implementation

  • store all elements at the leaves (N nodes)
  • each internal node is a competition (N-1 nodes)
  • insertion, deletion, update operations at O(log n) time; the bound is tight
  • can also use an array to store it
    • two children of A[i]: A[2i] and A[2i+1] (start from 1 can make it easier, but can also start from 0)
    • a complete binary tree
  • a good alternative to binary heap
    • same asymptotical bound for insertion/deletion/update/extract_min
    • easy to implement
    • takes more space, and is slightly slower in practice
    • when combining with augmentation, can be used to implement almost all data structures

References

Augmented trees

  • Range-related queries: 1D range max/min/sum
    • Extract-Min is a special range query (on the entire range)
  • We can augment the winning tree according to designated tasks
    • store different field for different query
    • often augment multiple fields at the same time
  • If we pre-sort all elements or the key range is fixed (e.g., entire range)
    • winning tree can be used as a static search tree
  • For floating-point range query, we can discretize it and map it to integers

Example Code: Greedy & Winner Tree (code to be improved)

#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <limits>
#include <functional>
​
struct node {
int key_min;
int key_max;
int value_min;
int value_max;
int idx;
};
​
// winner tree implementation
// faster, passed 8/10 cases
// the way to remove/update "used" nodes can be faster?
int main(){
int n, m;
std::cin >> n >> m;
std::vector<int> instructor(n);
for (int i = 0; i < n; ++i)
scanf("%d", &instructor[i]);
std::sort(instructor.begin(), instructor.end());
​
// construct (static) winner tree
std::vector<node> tree(2*m);
for (int i = m; i < 2*m; ++i) {
scanf("%d %d", &tree[i].key_max, &tree[i].value_min); // key, value --> student start day, end day
tree[i].idx = i;
tree[i].key_min = tree[i].key_max;
tree[i].value_max = tree[i].value_min;
}
for (int i = m-1; i > 0; --i) { // leave idx 0 unused
tree[i].key_min = std::min(tree[2*i].key_min, tree[2*i+1].key_min); // save min key
tree[i].key_max = std::max(tree[2*i].key_max, tree[2*i+1].key_max); // save max key
tree[i].value_min = std::min(tree[2*i].value_min, tree[2*i+1].value_min); // save min value
tree[i].value_max = std::max(tree[2*i].value_max, tree[2*i+1].value_max); // save max value
tree[i].idx = tree[2*i].value_min < tree[2*i+1].value_min ? tree[2*i].idx : tree[2*i+1].idx; // save min value idx
}
​
// this recursive function is the critical part
std::function<void(int,int,int,int&,int&)> range_min = [&tree, &range_min, &m](int i, int key_right, int value_left, int& min_value, int& idx){
if (i >= 2*m) return;
if (tree[i].key_min > key_right || tree[i].value_max < value_left) return;
if (tree[i].key_max <= key_right && value_left <= tree[i].value_min){
if(min_value > tree[i].value_min){
min_value = tree[i].value_min;
idx = tree[i].idx;
}
return;
}
range_min(i*2, key_right, value_left, min_value, idx);
range_min(i*2+1, key_right, value_left, min_value, idx);
};
​
auto tree_update = [&tree](int i, int new_value){
tree[i].value_min = new_value;
tree[i].value_max = new_value;
while (i > 1){
i = i / 2;
tree[i].value_min = std::min(tree[2*i].value_min, tree[2*i+1].value_min); // save min value
tree[i].value_max = std::max(tree[2*i].value_max, tree[2*i+1].value_max); // save max value
tree[i].idx = tree[2*i].value_min < tree[2*i+1].value_min ? tree[2*i].idx : tree[2*i+1].idx; // save min value idx
}
};
int max_num_students = 0;
for (auto& ins_day : instructor) { // O(n)
int earliest_stu_end_day = std::numeric_limits<int>::max();
int earliest_idx = -1;
range_min(1, ins_day, ins_day, earliest_stu_end_day, earliest_idx); // O(log(m))
if (earliest_idx == -1) continue;
tree_update(earliest_idx, std::numeric_limits<int>::max()); // O(log(m))
max_num_students++;
}
std::cout << max_num_students << std::endl;
​
return 0;
}