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

• TheAlgorithms/C-Plus-Plus: medium quality C++ code, but comprehensive

• Algorithm-DataStructures: high quality C++ code (and a few in other languages)

• Segment Tree

  • C++ implementation

  • Tutorial in Chinese

  • Tutorial on CodeForces

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;
}