1
var SORTracker = function () {
2
  (this.S = new AVL()), (this.i = 1);
3
};
4
SORTracker.prototype.add = function (name, score) {
5
  this.S.insert([name, score]);
6
};
7
SORTracker.prototype.get = function () {
8
  return this.S.findKthNODE(this.i++)[0];
9
};
10

11
// B O I  L E R P L A T E
12
class AVL {
13
  constructor() {
14
    this.nodeCount = 0;
15
    this.root = null;
16

17
    // MODIFY THIS EVERY TIME.
18
    this.NODE = class {
19
      constructor(
20
        val,
21
        left = null,
22
        right = null,
23
        parent = null,
24
        bf = 0,
25
        height = 0
26
      ) {
27
        this.val = val;
28
        (this.left = left), (this.right = right), (this.parent = parent);
29
        (this.bf = bf), (this.height = height);
30
        this.SubTreeNodes = 1;
31
      }
32
    };
33
  }
34

35
  //===M O D I F Y   FOR     COMPLEX     NODES==\\
36
  NODIFY(val) {
37
    //should return a new node based on the stats given
38
    return new this.NODE(val);
39
  }
40
  comparator = (node1, node2) => {
41
    // basic comparator that returns <0,0,>0 if node1>node2,node1==node2,node1<node2
42
    if (node1.val[1] === node2.val[1]) {
43
      if (node2.val[0] > node1.val[0]) return -1;
44
      return 1;
45
    }
46
    return Number(node2.val[1]) - Number(node1.val[1]);
47
  };
48
  //-------------U S A B L E------------------\\
49
  //returns true if the value was inserted successfully
50
  //returns false if the value already exists
51
  insert(NODE) {
52
    //O(logn)
53
    if (NODE === null) return false;
54
    NODE = this.NODIFY(NODE);
55
    if (!this.contains(this.root, NODE)) {
56
      this.root = this.ins(this.root, NODE);
57
      this.nodeCount++;
58
      return true;
59
    }
60
    return false;
61
  }
62
  remove(NODE) {
63
    if (NODE === null) return false;
64
    NODE = this.NODIFY(NODE);
65
    // console.log(this.contains(this.root,new Node(7)))
66
    if (this.contains(this.root, NODE)) {
67
      this.root = this.rem(this.root, NODE);
68
      this.nodeCount--;
69
      return true;
70
    }
71
    return false;
72
    //rebalance the tree
73
  }
74
  has(NODE) {
75
    NODE = this.NODIFY(NODE);
76
    return this.contains(this.root, NODE);
77
  }
78
  traversalASC() {
79
    //O(n)
80
    let result = [];
81
    let dfs = (node) => {
82
      if (!node) return;
83
      dfs(node.left);
84
      result.push(node);
85
      dfs(node.right);
86
    };
87
    dfs(this.root);
88
    return result;
89
  }
90
  findNextSmaller(NODE) {
91
    NODE = this.NODIFY(NODE);
92
    let cur = this.root,
93
      result = null;
94
    while (cur !== null) {
95
      if (this.comparator(cur, NODE) < 0) (result = cur), (cur = cur.right);
96
      else cur = cur.left;
97
    }
98
    if (result === null) return false; // no such element
99
    return result;
100
  }
101
  findNextBigger(NODE) {
102
    NODE = this.NODIFY(NODE);
103
    let cur = this.root,
104
      result = null;
105
    while (cur !== null) {
106
      if (this.comparator(cur, NODE) <= 0) cur = cur.right;
107
      else (result = cur), (cur = cur.left);
108
    }
109
    if (result === null) return false; // no such element
110
    return result;
111
  }
112
  findKthNODE(k) {
113
    //RETURNS THE NODE, NOT THE VALUE
114
    if (this.nodeCount < k) return null;
115
    return this.findKth(this.root, k);
116
  }
117
  min = () => this.findMin(this.root).val;
118
  max = () => this.findMax(this.root).val;
119
  //--------- I N T E R N A L S -----------------\\
120
  contains(node, val) {
121
    if (node === null) return false;
122
    let compare = this.comparator(node, val);
123
    if (compare < 0)
124
      //node<val
125
      return this.contains(node.right, val);
126
    if (compare > 0) return this.contains(node.left, val);
127
    return true;
128
  }
129
  //inserts newNode to target node
130
  ins(tree, value) {
131
    if (tree === null) return value;
132
    //(target is bigger? insert it to the left): else to the right
133
    if (this.comparator(tree, value) > 0)
134
      tree.left = this.ins(tree.left, value);
135
    else tree.right = this.ins(tree.right, value);
136
    //update balance factor of the target
137
    this.update(tree);
138
    return this.rebalance(tree); //balance the target if it needs rebalancing
139
  }
140
  rem(node, elem) {
141
    if (node === null) return null;
142
    //search an existing node with the given value
143
    let compare = this.comparator(elem, node); //-----
144
    if (compare < 0) node.left = this.rem(node.left, elem);
145
    else if (compare > 0) node.right = this.rem(node.right, elem);
146
    else {
147
      //node found
148
      //remove the node and replace it with its sucessor
149
      if (node.left === null) return node.right;
150
      else if (node.right === null) return node.left;
151
      else {
152
        //still has both subtrees?
153
        if (node.left.height > node.right.height) {
154
          let successor = this.findMax(node.left); /////
155
          node.val = successor.val;
156
          node.left = this.rem(node.left, successor);
157
        } else {
158
          let successor = this.findMin(node.right);
159
          node.val = successor.val;
160
          node.right = this.rem(node.right, successor);
161
        }
162
      }
163
    }
164
    this.update(node);
165
    return this.rebalance(node);
166
  }
167
  //find the min and max node of the subtree rooted at (node)
168
  findMin = (node) => (node.left ? this.findMin(node.left) : node);
169
  findMax = (node) => (node.right ? this.findMax(node.right) : node);
170
  //balances the subtree rooted at node if it is imbalanced (has balancefactor=+-2)
171
  //and returns the now balanced node
172
  rebalance(node) {
173
    //4 cases, 4 rotations
174
    if (node.bf == -2) {
175
      if (node.left.bf <= 0) return this.LL(node);
176
      else return this.LR(node);
177
    } else if (node.bf == 2) {
178
      if (node.right.bf >= 0) return this.RR(node);
179
      else return this.RL(node);
180
    }
181
    return node;
182
  }
183
  //update the balance factor and the height of the current node
184
  update(node) {
185
    let leftHeight = node.left !== null ? node.left.height : -1,
186
      rightHeight = node.right !== null ? node.right.height : -1;
187
    node.height = Math.max(leftHeight, rightHeight) + 1;
188
    node.bf = rightHeight - leftHeight;
189
    node.SubTreeNodes =
190
      1 +
191
      (node.left === null ? 0 : node.left.SubTreeNodes) +
192
      (node.right === null ? 0 : node.right.SubTreeNodes);
193
  }
194

195
  //4 cases of unbalanced trees
196
  LL = (node) => this.rightRotation(node);
197
  RR = (node) => this.leftRotation(node);
198
  LR(node) {
199
    node.left = this.leftRotation(node.left);
200
    return this.LL(node);
201
  }
202
  RL(node) {
203
    node.right = this.rightRotation(node.right);
204
    return this.RR(node);
205
  }
206
  //2 total rotations that work on RR and LL cases
207
  leftRotation(node) {
208
    let newParent = node.right;
209
    node.right = newParent.left;
210
    newParent.left = node;
211
    this.update(node);
212
    this.update(newParent);
213
    return newParent;
214
  }
215
  rightRotation(node) {
216
    let newParent = node.left;
217
    node.left = newParent.right;
218
    newParent.right = node;
219
    this.update(node);
220
    this.update(newParent);
221
    return newParent;
222
  }
223
  findKth(node, k) {
224
    let leftCount = node.left ? node.left.SubTreeNodes : 0;
225
    if (leftCount + 1 === k) return node.val;
226
    if (leftCount + 1 < k) return this.findKth(node.right, k - leftCount - 1);
227

228
    return this.findKth(node.left, k);
229
  }
230
}