Какие алгоритмы балансировки деревьев вам известны?

Существует несколько основных алгоритмов балансировки деревьев:

• Алгоритмы, основанные на поворотах (rotation-based algorithms): Эти алгоритмы поддерживают баланс, выполняя операции поворота при вставке или удалении узлов.

  • AVL-деревья (Adelson-Velsky and Landis trees): Поддерживают условие, что для каждого узла разница высот левого и правого поддеревьев не превышает 1.

  struct Node {
      int key;
      Node *left, *right;
      int height;
  };
  
  // Функция для получения высоты узла
  int height(Node *N) {
      if (N == NULL)
          return 0;
      return N->height;
  }
  
  // Функция для вычисления баланса узла
  int getBalance(Node *N) {
      if (N == NULL)
          return 0;
      return height(N->left) - height(N->right);
  }
  
  // Правый поворот
  Node *rightRotate(Node *y) {
      Node *x = y->left;
      Node *T2 = x->right;
  
      x->right = y;
      y->left = T2;
  
      y->height = 1 + max(height(y->left), height(y->right));
      x->height = 1 + max(height(x->left), height(x->right));
  
      return x;
  }
  

  • Красно-черные деревья (Red-Black trees): Поддерживают баланс, назначая узлам цвета (красный или черный) и соблюдая набор правил.

  enum Color { RED, BLACK };
  
  struct Node {
      int key;
      Node *left, *right, *parent;
      Color color;
  };
  
  // Функция для вставки узла и балансировки
  Node* insert(Node* root, Node* pt) {
      // Стандартная вставка BST
      if (root == NULL) return pt;
  
      if (pt->key < root->key) {
          root->left = insert(root->left, pt);
          root->left->parent = root;
      } else if (pt->key > root->key) {
          root->right = insert(root->right, pt);
          root->right->parent = root;
      }
  
      return root; // TODO: Реализация балансировки
  }
  

• Декартовы деревья (Treaps): Сочетают свойства двоичных деревьев поиска и куч (heaps). Каждый узел имеет ключ и приоритет. Построены таким образом, что являются деревом поиска по ключам и кучей по приоритетам.

• B-деревья и их вариации (B-trees, B+-trees, B-trees):* Чаще используются для работы с данными на внешних носителях (дисках) из-за минимизации операций ввода/вывода. У каждого узла может быть несколько дочерних элементов.

  Алгоритм	Свойства	Применение
  AVL-деревья	Строго сбалансированы по высоте. Быстрые операции поиска.	Поиск в памяти.
  Красно-черные деревья	Не строго сбалансированы по высоте, но гарантируется логарифмическая высота. Быстрые операции вставки/удаления.	Множества (std::set), карты (std::map) в C++.
  Декартовы деревья	Сбалансированы вероятностно. Простые операции вставки/удаления.	Структуры данных, требующие случайной балансировки.
  B-деревья	Оптимизированы для дисковых операций.	Файловые системы, базы данных.