Рубрики

Сложность различных операций в двоичном дереве, двоичном дереве поиска и дереве AVL

В этой статье мы обсудим сложность различных операций в двоичных деревьях, включая деревья BST и AVL. Прежде чем приступить к пониманию этой статьи, вы должны иметь представление о: двоичном дереве , двоичном дереве поиска и дереве AVL .

Основные операции в двоичном дереве: поиск, вставка и удаление. Мы увидим наихудшую временную сложность этих операций в двоичных деревьях.

Двоичное дерево —
В двоичном дереве у узла может быть максимум два потомка. Рассмотрим левое перекошенное двоичное дерево, показанное на рисунке 1.

  • Поиск: Для поиска элемента 2 мы должны пройти все элементы (при условии, что мы делаем первый обход в ширину). Следовательно, поиск в двоичном дереве имеет сложность O (n) в худшем случае.
  • Вставка: Для вставки элемента как левого потомка 2, мы должны пройти все элементы. Следовательно, вставка в двоичном дереве имеет сложность O (n) в худшем случае.
  • Удаление: Для удаления элемента 2 мы должны пройти все элементы, чтобы найти 2 (при условии, что мы делаем первый обход в ширину). Следовательно, удаление в двоичном дереве имеет сложность O (n) в худшем случае.

Двоичное дерево поиска (BST) —
BST — это особый тип двоичного дерева, в котором левый потомок узла имеет значение меньше, чем родительский, а правый потомок имеет значение больше, чем родительский. Рассмотрим перекошенный BST слева, показанный на рисунке 2.

  • Поиск: Для поиска элемента 1 мы должны пройти все элементы (в порядке 3, 2, 1). Следовательно, поиск в двоичном дереве поиска имеет наихудшую сложность O (n). В общем случае временная сложность равна O (h), где h — высота BST.
  • Вставка: Для вставки элемента 0 он должен быть вставлен как левый потомок 1. Поэтому нам нужно пройти все элементы (в порядке 3, 2, 1), чтобы вставить 0, который имеет наихудшую сложность O (n). В общем случае сложность времени равна O (h).
  • Удаление: Для удаления элемента 1 мы должны пройти все элементы, чтобы найти 1 (в порядке 3, 2, 1). Следовательно, удаление в двоичном дереве имеет сложность O (n) в худшем случае. В общем случае сложность времени равна O (h).

AVL / Высота Сбалансированного Дерева —
Дерево AVL — это двоичное дерево поиска с дополнительным свойством, заключающимся в том, что разница между высотой левого поддерева и правого поддерева любого узла не может быть больше 1. Например, BST, показанный на рисунке 2, не является AVL, поскольку разница между левым подпунктом -дерево и правое поддерево узла 3 равно 2. Однако BST, показанный на рисунке 3, является деревом AVL.

  • Поиск: Для поиска элемента 1 мы должны пройти элементы (в порядке 5, 4, 1) = 3 = log 2 n. Следовательно, поиск в дереве AVL имеет сложность O в худшем случае (log 2 n).
  • Вставка: Для вставки элемента 12 он должен быть вставлен как правый дочерний элемент для 9. Поэтому нам нужно пройти элементы (в порядке 5, 7, 9), чтобы вставить 12, который имеет наихудшую сложность O (log 2 n).
  • Удаление: Для удаления элемента 9 мы должны пройти элементы, чтобы найти 9 (в порядке 5, 7, 9). Следовательно, удаление в двоичном дереве имеет сложность O в худшем случае (log 2 n).

Мы обсудим вопросы, основанные на сложностях операций с двоичным деревом.

Que-1. Какова сложность времени наихудшего случая для операций поиска, вставки и удаления в общем бинарном дереве поиска?
(A) O (n) для всех
(B) O (Logn) для всех
(C) O (Logn) для поиска и вставки и O (n) для удаления
(D) O (Logn) для поиска и O (n) для вставки и удаления

Решение: Как обсуждалось, все операции в BST имеют наихудшую временную сложность O (n). Таким образом, правильный вариант (А).

Que-2. Каковы наихудшие временные сложности поиска в двоичном дереве, дереве BST и AVL соответственно?
(A) O (n) для всех
(B) O (Logn) для всех
(C) O (n) для двоичного дерева и O (Logn) для других
(D) O (n) для двоичного дерева и BST и O (Logn) для AVL

Решение: Как обсуждалось, операция поиска в двоичном дереве и BST имеет наихудшую временную сложность O (n). Однако дерево AVL имеет наихудшую временную сложность O (logn). Таким образом, правильный вариант (D).

Рекомендуемые посты:

Сложность различных операций в двоичном дереве, двоичном дереве поиска и дереве AVL

0.00 (0%) 0 votes