Стратегия создания BBST, когда мы знаем, что большинство вставок в порядке?

У меня есть ситуация, когда мне нужно сбалансированное бинарное дерево поиска. Я использовал дерево AVL, но оно требует много поворотов для создания высоты баланса при вставке. Я заметил, что большинство входов уже в порядке. Например: 8 9 10 11 12 13 2 14 15 16 17 4 18 19 20 и т. Д. Есть ли лучшая стратегия создания BBST, когда мы знаем, что большинство входов уже в порядке?

Источник

3 ответа

Решение

Запустите сортировку вставкой, которая имеет хорошую производительность для уже отсортированных или почти отсортированных массивов (она имеет производительность O(n + d), где d количество инверсий). Конечно, вы не захотите делать это, если массив вообще не отсортирован, и в этом случае потребуется O(n2), в отличие от других алгоритмов сортировки, которые принимают O(n log n),

После запуска вы можете построить BST вO(n):

Если бы вам пришлось выбрать элемент массива в качестве корня сбалансированного BST, какой элемент вы бы выбрали? Корнем сбалансированного BST должен быть средний элемент из отсортированного массива.

Вы должны выбрать средний элемент из отсортированного массива в каждой итерации. Затем вы создаете узел в дереве, инициализированный этим элементом. После того, как элемент выбран, что осталось? Не могли бы вы определить подзадачи в рамках проблемы?

Осталось два массива - один слева и один справа. Эти два массива являются подзадачами исходной задачи, поскольку оба они отсортированы. Кроме того, они являются поддеревьями левого и правого дочернего узла текущего узла.

Источник

Сортировать входы, используя сортировку вставкой; обычно это алгоритм O(n^2), но O(n), если вход почти отсортирован. Затем поместите средний элемент ввода в корень дерева, рекурсивно поместите средний элемент левой половины ввода в корень левого поддерева корня, а средний элемент правой половины ввода - в поле. корень правого поддерева корня и т. д., пока весь ввод не будет в дереве.

Источник

Предположим, что arr - почти отсортированный массив, тогда вы можете сделать следующее, чтобы получить из него хорошее сбалансированное дерево:-

make_tree(BST,arr,high,low) {

  if(high>=low) {

      mid = (high+low)/2;
      BST.insert(arr[mid]);
      make_tree(BST,arr,mid-1,low);
      make_tree(BST,arr,high,mid+1);
  }

}

make_tree(BST,arr,N-1,0);

Объяснение:- Поскольку массив почти отсортирован, мы делим его на равные половины, средняя сложность вставки по времени O(logN) и, следовательно, сложность времени O(nlogn)

Источник
Другие вопросы по тегам