Inorder: z → x → t → y.

Формула bf работает только если высоты актуальны. Порядок после вставки:

1. Вставить ключ как в BST (спуск вниз)
2. Подниматься к корню: на каждом узле updateHeight
3. На каждом узле посчитать bf
4. При |bf| = 2 — поворот по таблице случаев
5. После поворота — снова updateHeight у затронутых узлов

Лист без детей: height = 1, bf = 0. Пустой сын в формуле дает вклад 0.

Красно-черное дерево (Guibas, Sedgewick) — самобалансирующееся БДП. Баланс мягче, чем у AVL, зато вставки и удаления обычно дешевле.

Новый узел ставится как в BST и красится в красный, потому что красный узел не увеличивает черную высоту пути.

Куча — complete-бинарное дерево, хранящееся в массиве: все уровни заполнены, а последний заполняется слева направо. Главное правило — не порядок «слева меньше», а отношение родитель ↔ дети.

На семинаре — только min-heap (minHeap.cpp).

lib/treeAlgs/avlTree.cpp — дописать тела функций

rotateRight(y, rot):
  ++(*rot); x = y.left; t = x.right
  x.right = y; y.left = t
  updateHeight(y); updateHeight(x)
  return x

rotateLeft(x, rot):  // зеркально
  ++(*rot); y = x.right; t = y.left
  y.left = x; x.right = t
  updateHeight(x); updateHeight(y)
  return y

rebalance(node, rot):
  updateHeight(node); bf = balanceFactor(node)
  if bf > +1:
    if balanceFactor(node.left) < 0:
      node.left = rotateLeft(node.left, rot)
    return rotateRight(node, rot)
  if bf < -1:
    if balanceFactor(node.right) > 0:
      node.right = rotateRight(node.right, rot)
    return rotateLeft(node, rot)
  return node

avlInsert(root, key, rot):
  if !root: return new AvlNode(key)
  if key < root.key:
    root.left = avlInsert(left, key, rot)
  else if key > root.key:
    root.right = avlInsert(right, key, rot)
  else: return root    // дубликат
  return rebalance(root, rot)

avlSize(root):
  if !root: return 0
  return 1 + avlSize(left) + avlSize(right)

avlInorder: как binInorder — left, key, right
avlFree: postorder delete (как binFree)

В draft пустые не только повороты: дописать также avlSize, avlInorder, avlFree. task41001.cpp вызывает avlInsert, avlSize, avlHeight.

lib/treeAlgs/minHeap.cpp

heapInit(h, buffer, cap):
  h.data = buffer; h.size = 0; h.capacity = cap

siftUp(h, i):  // вспомогательно; 4.10.03 напрямую push не вызывает
  while i > 0:
    p = (i - 1) / 2
    if h.data[p] <= h.data[i]: break
    swap(h.data[p], h.data[i])
    i = p

siftDown(h, i):
  loop:
    l = 2*i + 1; r = l + 1
    smallest = i
    if l < h.size and h.data[l] < h.data[smallest]: smallest = l
    if r < h.size and h.data[r] < h.data[smallest]: smallest = r
    if smallest == i: break
    swap(h.data[i], h.data[smallest]); i = smallest

heapBuild(h, keys, n):
  if !h or !h.data or n < 0 or n > h.capacity: return false
  скопировать keys[0..n-1] в h.data
  h.size = n
  for i = n/2 - 1 .. 0:    // снизу вверх
    siftDown(h, i)
  return true

heapExtractMin(h, valueOut):
  if !h or h.size <= 0 or !valueOut: return false
  *valueOut = h.data[0]
  h.data[0] = h.data[h.size - 1]
  --h.size
  if h.size > 0: siftDown(h, 0)
  return true

task41003.cpp: heapInit, heapBuild, затем q раз heapExtractMin → строки Extract: k. siftUp полезен для понимания push, но в task-файле не вызывается.

Порядок сложности

1. minHeap.cpp — массив, без указателей
2. avlTree.cpp — повороты, высоты
3. rbTree.cpp — самый объемный fixup

Не копируйте reference целиком — разберите каждый случай.