AVL-дерево

1class AVLNode {
2  value: number
3  left: AVLNode | null = null
4  right: AVLNode | null = null
5  height = 1
6 
7  balance(): number {
8    return h(this.right) - h(this.left)
9  }
10}
11 
12function insert(node: AVLNode | null, v: number): AVLNode {
13  if (node === null) return new AVLNode(v)
14  if (v < node.value) node.left = insert(node.left, v)
15  else node.right = insert(node.right, v)
16 
17  node.height = 1 + Math.max(h(node.left), h(node.right))
18 
19  const b = node.balance()
20  if (b < -1 && v < node.left!.value) return rotateRight(node)      // LL
21  if (b > 1 && v > node.right!.value) return rotateLeft(node)       // RR
22  if (b < -1) { node.left = rotateLeft(node.left!);  return rotateRight(node) } // LR
23  if (b > 1)  { node.right = rotateRight(node.right!); return rotateLeft(node) } // RL
24 
25  return node
26}