Двоичное дерево: Бинарные деревья поиска и рекурсия

Содержание

Разница между «полным двоичным деревом»,»строгим двоичным деревом», «полным двоичным деревом»?

Чтобы начать с основ, очень важно понять само бинарное дерево, чтобы понять его различные типы.

Дерево является двоичным деревом тогда и только тогда, когда :-

– Он имеет корневой узел , который может не иметь никаких дочерних узлов (0 childnodes, NULL tree)

— Корневой узел может иметь 1 или 2 дочерних узла . Каждый такой узел сам образует абинарное дерево

–Количество дочерних узлов может быть 0, 1, 2…….not больше 2

–Существует уникальный путь от корня к каждому другому узлу

Пример :

Переходя к вашей запрашиваемой терминологии:

Двоичное дерево — это полное двоичное дерево (высоты h, мы берем корневой узел как 0 ) тогда и только тогда, когда :-

Уровень от 0 до h-1 представляет собой полное двоичное дерево высоты h-1

– Один или несколько узлов на уровне h-1 могут иметь 0 или 1 дочерний узел

Если j, k являются узлами на уровне h-1, то j имеет больше дочерних узлов, чем k тогда и только тогда, когда j находится слева от k , то есть последний уровень (h) может быть отсутствующим листовым узлом, однако присутствующие должны быть сдвинуты влево

Пример :

                          X
                     /          \
                   /              \
                 /                  \
                X                    X
             /     \              /     \
           X       X             X       X
         /   \   /   \         /   \    /  \ 
        X    X   X   X        X    X    X   X

Двоичное дерево является строго двоичным деревом тогда и только тогда, когда :-

Каждый узел имеет ровно два дочерних узла или не имеет узлов

Пример :

         X
       /   \
      X     X 
          /   \
         X      X
        / \    / \ 
       X   X  X   X

Двоичное дерево является полным двоичным деревом тогда и только тогда, когда :-

Каждый не листовой узел имеет ровно два дочерних узла

Все листовые узлы находятся на одном уровне

Пример :

                          X
                     /          \
                   /              \
                 /                  \
                X                    X
             /     \              /     \
           X       X             X       X
         /   \   /   \         /   \    /  \ 
        X    X   X   X        X    X    X   X 
      /  \  / \ / \ / \      / \  / \  / \ / \ 
     X   X X  X X X X X     X  X  X X  X X X X

Вы также должны знать, что такое идеальное двоичное дерево?

Двоичное дерево является идеальным двоичным деревом тогда и только тогда, когда :-

— это полное двоичное дерево

– Все листовые узлы находятся на одном уровне

Пример :

                          X
                     /          \
                   /              \
                 /                  \
                X                    X
             /     \              /     \
           X       X             X       X
         /   \   /   \         /   \    /  \ 
        X    X   X   X        X    X    X   X 
      /  \  / \ / \ / \      / \  / \  / \ / \ 
     X   X X  X X X X X     X  X  X X  X X X X

Ну, мне очень жаль, что я не могу публиковать изображения, так как у меня нет репутации 10.
Надеюсь, это поможет вам и другим!

Двоичное дерево поиска, определение свойства, операции Струк…

Привет, сегодня поговорим про двоичное дерево поиска определение свойства операции, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое
двоичное дерево поиска определение свойства операции , настоятельно рекомендую прочитать все из категории Структуры данных

Двоичное дерево поиска
Тип	Дерево
Временная сложность в О-символике
	В среднем	В худшем случае
Расход памяти	O(n)	O(n)
Поиск	O(log n)	O(n)
Вставка	O(log n)	O(n)
Удаление	O(log n)	O(n)

Содержание

Опредеение и свойства Двоичного дерева поиска, операции

1 Основные операции в двоичном дереве поиска
- 1.1 Поиск элемента (FIND)
- 1.2 Добавление элемента (INSERT)
- 1.3 Удаление узла (REMOVE)
- 1.4 Обход дерева (TRAVERSE)
- 1.5 Разбиение дерева по ключу
- 1.6 Объединение двух деревьев в одно

2 Балансировка дерева

3 Задачи о бинарном дереве поиска

Двоичное дерево поиска (англ. binary search tree, BST) — это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

Оба поддерева — левое и правое — являются двоичными деревьями поиска.

У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.

В то время, как значения ключей данных у всех узлов правого поддерева (того же узла X) больше, нежели значение ключа данных узла X.

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

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

Пример двоичного дерева поиска

Для целей реализации двоичное дерево поиска можно определить так:

Двоичное дерево состоит из узлов (вершин) — записей вида (data, left, right), где data — некоторые данные, привязанные к узлу, left и right — ссылки на узлы, являющиеся детьми данного узла — левый и правый сыновья соответственно. Для оптимизации алгоритмов конкретные реализации предполагают также определения поля parent в каждом узле (кроме корневого) — ссылки на родительский элемент.

Данные (data) обладают ключом (key), на котором определена операция сравнения «меньше». В конкретных реализациях это может быть пара (key, value) — (ключ и значение), или ссылка на такую пару, или простое определение операции сравнения на необходимой структуре данных или ссылке на нее.

Для любого узла X выполняются свойства дерева поиска: key[left[X]] < key[X] ≤ key[right[X]], то есть ключи данных родительского узла больше ключей данных левого сына и нестрого меньше ключей данных правого.

Двоичное дерево поиска не следует путать с двоичной кучей, построенной по другим правилам.

Основным преимуществом двоичного дерева поиска перед другими структурами данных является возможная высокая эффективность реализации основанных на нем алгоритмов поиска и сортировки.

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

Основные операции в двоичном дереве поиска

Базовый интерфейс двоичного дерева поиска состоит из трех операций:

FIND(K) — поиск узла, в котором хранится пара (key, value) с key = K.

INSERT(K,V) — добавление в дерево пары (key, value) = (K, V).

REMOVE(K) — удаление узла, в котором хранится пара (key, value) с key = K.

Этот абстрактный интерфейс является общим случаем, например, таких интерфейсов, взятых из прикладных задач:

«Телефонная книжка» — хранилище записей (имя человека, его телефон) с операциями поиска и удаления записей по имени человека, и операцией добавления новой записи.

Domain Name Server — хранилище пар (доменное имя, IP адрес) с операциями модификации и поиска.

Namespace — хранилище имен переменных с их значениями, возникающее в трансляторах языков программирования.

По сути, двоичное дерево поиска — это структура данных, способная хранить таблицу пар (key, value) и поддерживающая три операции: FIND, INSERT, REMOVE.

Кроме того, интерфейс двоичного дерева включает еще три дополнительных операции обхода узлов дерева: INFIX_TRAVERSE, PREFIX_TRAVERSE и POSTFIX_TRAVERSE. Первая из них позволяет обойти узлы дерева в порядке неубывания ключей.

Поиск элемента (FIND)

Дано: дерево Т и ключ K.

Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел.

Алгоритм:

Если дерево пусто, сообщить, что узел не найден, и остановиться.

Иначе сравнить K со значением ключа корневого узла X.
- Если K=X, выдать ссылку на этот узел и остановиться.
- Если K>X, рекурсивно искать ключ K в правом поддереве Т.
- Если K

Поиск элемента (дополнитеьный пример)

Поиск элемента 4

Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы O(h)O(h), где hh — высота дерева.


Node search(x : Node, k : T):
   if x == null or k == x.key
      return x
   if k < x.key
      return search(x.left, k)
   else
      return search(x.right, k)

Поиск минимума и максимума

Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям leftleft от корня дерева, пока не встретится значение nullnull. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.


Node minimum(x : Node):
  if x.left == null
     return x
  return minimum(x.left)


Node maximum(x : Node):
  if x.right == null
     return x
  return maximum(x.right)

Данные функции принимают корень поддерева, и возвращают минимальный (максимальный) элемент в поддереве. Обе процедуры выполняются за время O(h)O(h).

Поиск следующего и предыдущего элемента

Реализация с использованием информации о родителе

Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.


Node next(x : Node):
   if x.right != null
      return minimum(x.right)
   y = x.parent
   while y != null and x == y.right
      x = y
      y = y.parent
   return y


Node prev(x : Node):
   if x.left != null
      return maximum(x.left)
   y = x.parent
   while y != null and x == y.left
      x = y
      y = y.parent
   return y

Обе операции выполняются за время O(h)O(h).

Реализация без использования информации о родителе

Рассмотрим поиск следующего элемента для некоторого ключа xx . Об этом говорит сайт https://intellect.icu . Поиск будем начинать с корня дерева, храня текущий узел currentcurrent и узел successorsuccessor, последний посещенный узел, ключ которого больше xx.

Спускаемся вниз по дереву, как в алгоритме поиска узла. Рассмотрим ключ текущего узла currentcurrent. Если current.key⩽xcurrent. key⩽x, значит следующий за xx узел находится в правом поддереве (в левом поддереве все ключи меньше current.keycurrent.key). Если же x<current.keyxx<next(x)⩽current.keyxcurrentcurrent может быть следующим для ключа xx, либо следующий узел содержится в левом поддереве currentcurrent. Перейдем к нужному поддереву и повторим те же самые действия.

Аналогично реализуется операция поиска предыдущего элемента.


Node next(x : T):
   Node current = root, successor = null                // root — корень дерева
   while current != null
      if current.key > x
         successor = current
         current = current.left
      else
         current = current.right
   return successor

Добавление(вставка) элемента (INSERT)

Дано: дерево Т и пара (K,V).

Задача: вставить пару (K, V) в дерево Т (при совпадении K, заменить V).

Алгоритм:

Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), null, null) и остановиться.

Иначе сравнить K с ключом корневого узла X.
- Если K>X, циклически добавить (K,V) в правое поддерево Т.
- Если K
- Если K=X, заменить V текущего узла новым значением. (хотя можно и организовать список значений V, но это другая тема)

Второй пример

Операция вставки работает аналогично поиску элемента, только при обнаружении у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент.

Реализация с использованием информации о родителе


func insert(x : Node, z : Node):            // x — корень поддерева, z — вставляемый элемент
   while x != null
     if z.key > x.key
        if x.right != null
           x = x.right
        else
           z.parent = x
           x.right = z
           break
     else if z.key < x.key
        if x.left != null
           x = x.left
        else
           z.parent = x
           x.left = z
           break

Реализация без использования информации о родителе


Node insert(x : Node, z : T):               // x — корень поддерева, z — вставляемый ключ
   if x == null
      return Node(z)                        // подвесим Node с key = z
   else if z < x.key
      x.left = insert(x.left, z)
   else if z > x.key
      x.right = insert(x.right, z)
   return x

Время работы алгоритма для обеих реализаций — O(h)O(h).

Удаление узла (REMOVE)

Дано: дерево Т с корнем n и ключом K.

Задача: удалить из дерева Т узел с ключом K (если такой есть).

Алгоритм:

Если дерево T пусто, остановиться;

Иначе сравнить K с ключом X корневого узла n.
- Если K>X, циклически удалить K из правого поддерева Т;
- Если K
- Если K=X, то необходимо рассмотреть три случая.
  - Если обоих детей нет, то удаляем текущий узел и обнуляем ссылку на него у родительского узла;
  - Если одного из детей нет, то значения полей ребенка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m;
  - Если оба ребенка присутствуют, то
    - Если левый узел m правого поддерева отсутствует (n->right->left)
      - Копируем из (8) в (4) поля K, V и ссылку на правый узел.
    - Иначе
      - возьмем самый левый узел m, правого поддерева n->right;
      - скопируем данные (кроме ссылок на дочерние элементы) из m в n;
      - рекурсивно удалим узел m.

Удаление (второй пример)

Нерекурсивная реализация удаления узла из двоичного дерева поиска

Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на nullnull. Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент (у этого элемента не будет левого потомка), его правого потомка подвесить на место найденного элемента, а удаляемый узел заменить найденным узлом. Таким образом, свойство бинарного дерева поиска не будет нарушено. Данная реализация удаления не увеличивает высоту дерева. Время работы алгоритма — O(h)O(h).

Случай	Иллюстрация
Удаление листа
Удаление узла с одним дочерним узлом
Удаление узла с двумя дочерними узлами


func delete(t : Node, v : Node):                 // tt — дерево, vv — удаляемый элемент
   p = v.parent                                  // предок удаляемого элемента
   if v.left == null and v.right == null         // первый случай: удаляемый элемент - лист
     if p. left == v
       p.left = null
     if p.right == v
       p.right = null
   else if v.left == null or v.right == null     // второй случай: удаляемый элемент имеет одного потомка
       if v.left == null
           if p.left == v
             p.left = v.right
           else
             p.right = v.right
           v.right.parent = p
       else
           if p.left == v
               p.left = v.left
           else
               p.right = v.left
           v.left.parent = p
   else                                          // третий случай: удаляемый элемент имеет двух потомков
     successor = next(v, t)
     v.key = successor.key
     if successor.parent.left == successor
       successor.parent.left = successor.right
       if successor.right != null
         successor.right.parent = successor.parent
     else
       successor.parent.right = successor.left
       if successor.left != null
         successor.right.parent = successor.parent

Рекурсивная реализация удаления узла из двоичного дерева поиска

При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить этот минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма — O(h)O(h). Рекурсивная функция, возвращающая дерево с удаленным элементом zz:


Node delete(root : Node, z : T):               // корень поддерева, удаляемый ключ
  if root == null
    return root
  if z < root.key
    root.left = delete(root.left, z)
  else if z > root.key
    root.right = delete(root.right, z)
  else if root.left != null and root.right != null
    root.key = minimum(root.right).key
    root.right = delete(root.right, root.key)
  else
    if root.left != null
      root = root.left
    else
      root = root.right
  return root

Обход дерева (TRAVERSE)

Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов.

Первая операция — INFIX_TRAVERSE — позволяет обойти все узлы дерева в порядке возрастания ключей и применить к каждому узлу заданную пользователемфункцию обратного вызова f, операндом которой является адрес узла. Эта функция обычно работает только с парой (K,V), хранящейся в узле. Операция INFIX_TRAVERSE может быть реализована рекурсивным образом: сначала она запускает себя для левого поддерева, потом запускает данную функцию для корня, потом запускает себя для правого поддерева.

INFIX_TRAVERSE (tr) — обойти все дерево, следуя порядку (левое поддерево, вершина, правое поддерево). Элементы по возрастанию

PREFIX_TRAVERSE (tr) — обойти все дерево, следуя порядку (вершина, левое поддерево, правое поддерево). Элементы как в дереве

POSTFIX_TRAVERSE (tr) — обойти все дерево, следуя порядку (левое поддерево, правое поддерево’, вершина). Элементы в обратном порядке как в дереве

В других источниках эти функции именуются inorder, preorder, postorder соответственно[1]

INFIX_TRAVERSE

Дано: дерево Т и функция f

Задача: применить f ко всем узлам дерева Т в порядке возрастания ключей

Алгоритм:

Если дерево пусто, остановиться.

Иначе
- Рекурсивно обойти левое поддерево Т.
- Применить функцию f к корневому узлу.
- Рекурсивно обойти правое поддерево Т.

В простейшем случае, функция f может выводить значение пары (K,V). При использовании операции INFIX_TRAVERSE будут выведены все пары в порядке возрастания ключей. Если же использовать PREFIX_TRAVERSE, то пары будут выведены в порядке, соответствующим описанию дерева, приведенного в начале статьи.

Пример Обхода дерева поиска

Для представления бинарного дерева поиска в памяти будем использовать следующую структуру:


struct Node:
  T key                    // ключ узла
  Node left                // указатель на левого потомка
  Node right               // указатель на правого потомка
  Node parent              // указатель на предка

Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:

inorderTraversalinorderTraversal — обход узлов в отсортированном порядке,

preorderTraversalpreorderTraversal — обход узлов в порядке: вершина, левое поддерево, правое поддерево,

postorderTraversalpostorderTraversal — обход узлов в порядке: левое поддерево, правое поддерево, вершина.


func inorderTraversal(x : Node):
   if x != null
      inorderTraversal(x. left)
      print x.key
      inorderTraversal(x.right)

При выполнении данного обхода вершины будут выведены в следующем порядке: 1 3 4 6 7 8 10 13 14.


func preorderTraversal(x : Node)
   if x != null
      print x.key
      preorderTraversal(x.left)
      preorderTraversal(x.right)

При выполнении данного обхода вершины будут выведены в следующем порядке: 8 3 1 6 4 7 10 14 13.


func postorderTraversal(x : Node)
   if x != null
      postorderTraversal(x.left)
      postorderTraversal(x.right)
      print x.key

При выполнении данного обхода вершины будут выведены в следующем порядке: 1 4 7 6 3 13 14 10 8.

Данные алгоритмы выполняют обход за время O(n)O(n), поскольку процедура вызывается ровно два раза для каждого узла дерева.

Разбиение дерева по ключу

Операция «разбиение дерева по ключу» позволяет разбить одно дерево поиска на два: с ключами <K0 и ≥K0.

Объединение двух деревьев в одно

Обратная операция: есть два дерева поиска, у одного ключи <K0, у другого ≥K0. Объединить их в одно дерево.

У нас есть два дерева: T1 (меньшее) и T2 (большее). Сначала нужно решить, откуда взять корень: из T1 или T2. Стандартного метода нет, возможные варианты:

Взять наугад (см. декартово дерево).

Если в каждом узле дерева поддерживается размер всей ветви (см. дерево с неявным ключом), легко можно оценить дисбаланс для того и другого варианта.


алг ОбъединениеДеревьев(T1, T2)
если T1 пустое, вернуть T2
если T2 пустое, вернуть T1
если решили сделать корнем T1, то
  T = ОбъединениеДеревьев(T1. правое, T2)
  T1.правое = T
  вернуть T1
иначе
  T = ОбъединениеДеревьев(T1, T2.левое)
  T2.левое = T
  вернуть T2

Балансировка дерева

Всегда желательно, чтобы все пути в дереве от корня до листьев имели примерно одинаковую длину, то есть чтобы глубина и левого, и правого поддеревьев была примерно одинакова в любом узле. В противном случае теряется производительность.

В вырожденном случае может оказаться, что все левое дерево пусто на каждом уровне, есть только правые деревья, и в таком случае дерево вырождается в список (идущий вправо). Поиск (а значит, и удаление и добавление) в таком дереве по скорости равен поиску в списке и намного медленнее поиска в сбалансированном дереве.

Для балансировки дерева применяется операция « поворот дерева». Поворот налево выглядит так:

было Left(A) = L, Right(A) = B, Left(B) = C, Right(B) = R

поворот меняет местами A и B, получая Left(A) = L, Right(A) = C, Left(B) = A, Right(B) = R

также меняется в узле Parent(A) ссылка, ранее указывавшая на A, после поворота она указывает на B.

Поворот направо выглядит так же, достаточно заменить в вышеприведенном примере все Left на Right и обратно.

Достаточно очевидно, что поворот не нарушает упорядоченность дерева, и оказывает предсказуемое (+1 или −1) влияние на глубины всех затронутых поддеревьев.

Для принятия решения о том, какие именно повороты нужно совершать после добавления или удаления, используются такие алгоритмы, как « красно-черное дерево» иАВЛ.

Оба они требуют дополнительной информации в узлах — 1 бит у красно-черного или знаковое число у АВЛ.

Красно-черное дерево требует <= 2 поворотов после добавления и <= 3 после удаления, но при этом худший дисбаланс может оказаться до 2 раз (самый длинный путь в 2 раза длиннее самого короткого).

АВЛ-дерево требует <= 2 поворотов после добавления и до глубины дерева после удаления, но при этом идеально сбалансировано (дисбаланс не более, чем на 1).

Задачи о бинарном дереве поиска

Проверка того, что заданное дерево является деревом поиска

Задача:

Определить, является ли заданное двоичное дерево деревом поиска.

Пример дерева, для которого недостаточно проверки лишь его соседних вершин

Задачи на поиск максимального BST в заданном двоичном дереве

Задача:

Найти в данном дереве такую вершину, что она будет корнем поддерева поиска с наибольшим количеством вершин.

Восстановление дерева по результату обхода preorderTraversa

Задача:

Восстановить дерево по последовательности, выведенной после выполнения процедуры preorderTraversal.

Как мы помним, процедура preorderTraversal выводит значения в узлах поддерева следующим образом: сначала идет до упора влево, затем на каком-то моменте делает шаг вправо и снова движется влево. Это продолжается до тех пор, пока не будут выведены все вершины. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Первая вершина всегда будет в корне. Затем, пока не будут использованы все значения, будем последовательно подвешивать левых сыновей к последней добавленной вершине, пока не найдем номер, нарушающий убывающую последовательность, а для каждого такого номера будем искать вершину без правого потомка, хранящую наибольшее значение, не превосходящее того, которое хотим поставить, и подвешиваем к ней элемент с таким номером в качестве правого сына. Когда мы, желая найти такую вершину, встречаем какую-нибудь другую, уже имеющую правого сына, проходим по ветке вправо. Мы имеем на это право , так как если такая вершина стоит, то процедура обхода в ней уже побывала и поворачивала вправо, поэтому спускаться в другую сторону смысла не имеет. Вершину с максимальным ключом, с которой будем начинать поиск, будем запоминать. Она будет обновляться каждый раз, когда появится новый максимум.

Процедура восстановления дерева работает за O(n).

Разберем алгоритм на примере последовательности 8 2 1 4 3 5

Будем выделять красным цветом вершины, рассматриваемые на каждом шаге, черным жирным — их родителей, курсивом — убывающие подпоследовательности (в случаях, когда мы их рассматриваем) или претендентов на добавление к ним правого ребенка (когда рассматривается вершина, нарушающая убывающую последовательность).

См. также

Сбалансированные деревья :

Понравилась статья про двоичное дерево поиска определение свойства операции? Откомментируйте её Надеюсь, что теперь ты понял что такое двоичное дерево поиска определение свойства операции
и для чего все это нужно, а если не понял, или есть замечания,
то нестесняся пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории
Структуры данных

Бинарное (двоичное) дерево поиска, обходы и применение

Дерево — это один из абстрактных типов данных, а также любая структура данных, которая этот тип реализует. Деревья моделируют иерархичную древовидную структуру (ну например, семейное древо), в котором существует только один корень (корневой элемент) и узлы (другие элементы), связанные отношениями потомок — родитель, где любой отдельно взятый элемент имеет только одного родителя (кроме корня, у него-то родителей нет).

Ещё деревья можно определить рекурсивно: дерево может быть или пустым, или состоять из узла (корня), являющимся родительским узлом для некоторого количества деревьев. Количество дочерних узлов обозначает арность дерева; другими словами, n-арное дерево не может содержать более n дочерних элементов (далее дочерний узел, дочерний элемент и потомок будут иметь один и тот же смысл) для каждого узла. Арность дерева — это тоже самое, что и степень дерева. Если же для каждого узла дерева определяется индивидуальная степень, то говорят только про степень конкретных узлов.

Помимо этого необходимо знать ещё 2 понятия в разговоре о деревьях: путь до вершины (всегда начинаем от корня) и высота дерева (реже — глубина). Путь — это множество переходов в дереве, от корня к необходимому узлу. Число узлов в любом пути называется длиной пути, а максимальная длина пути из всех — высотой дерева. Поскольку дерево — частный случай графа, то такие переходы называют рёбрами, а узлы — вершинами.

Одной из форм записи деревьев «на бумаге» называется скобочной записью:

(8 (3 (1) (6 (4) (7))) (10 (14 (13))))

А для наглядности расставим пробелы и переносы:

А так оно выглядит на самом деле:

Бинарное дерево поиска

Деревья полезны, они используются во многих задачах, например:

парсеры и трансляторы используют синтаксическое дерево;
при работе со строками используются суффиксные деревья;
бинарные деревья используются в большом количестве задач: от сортировки и поиска, до создания на их базе других, более сложных структур данных.

Важно место в информатике занимают бинарные (или двоичные) деревья, у которых для каждого узла не более 2-х дочерних элементов, это левый и правый наследники. БНФ форма его определения выглядит так:


 ::= (    ) | nil

Существуют множество разных бинарных деревьев, например, двоичная куча (или сортирующее дерево). Оно используется в пирамидальной сортировке и при реализации приоритетных очередей. Для этого на обычное бинарное дерево нужно всего лишь наложить такие ограничения:

Значение в любой вершине не меньше, чем значения её потомков.
Глубина всех листьев (расстояние до корня) отличается не более чем на 1 слой.
Последний слой заполняется слева направо без «дырок».

А вот другое — бинарное дерево поиска. Используется для организации хранения данных таким образом, чтобы гарантировать поиск элемента за логарифмическое время:

Оба поддерева — левое и правое — являются двоичными деревьями поиска.
У всех узлов левого поддерева для произвольного узла значения ключей меньше значения ключа этого узла.
У всех узлов правого поддерева для произвольного узла значения ключей больше либо равны значения ключа этого узла.

Поиск элемента с заданным значением в таком дереве происходит очевидным образом: начиная с корня сравниваем текущее значение узла с заданным; если они равны, то значение найдено, иначе сравниваем значения и выбираем следующий узел для проверки: левый или правый.

Чтобы работать с деревьями, нужно уметь обходить его элементы. Существуют такие 3 варианта обхода:

Прямой обход (КЛП): корень → левое поддерево → правое поддерево.
Центрированный обход (ЛКП): левое поддерево → корень → правое поддерево.
Обратный обход (ЛПК): левое поддерево → правое поддерево → корень

Прямой обход

Центрированный обход

Обратный обход

Такие обходы называются поиском в глубину, поскольку на каждом шаге итератор пытается продвинуться вертикально вниз по дереву перед тем, как перейти к родственному узлу (узлу на том же уровне). Ещё существует поиск в ширину. Его суть в обходе узлов дерева по уровням, начиная с корня (нужно пройти всего лишь 1 узел) и далее (на втором 2 узла, на третьем 4 узла, ну и т.д.; сколько узлов надо пройти на k-м уровне?).

Обход в ширину

Реализация поиска в глубину может осуществляться или с использованием рекурсии или с использованием стека, а поиск в ширину реализуется за счёт использования очереди:

Рекурсивный:


preorder(node)
  if (node = null)
    return
  visit(node)
  preorder(node. left)
  preorder(node.right)

Через стек:


iterativePreorder(node)
  s ← empty stack
  s.push(node)
  while (not s.isEmpty())
    node ← s.pop()
    visit(node)
    if (node.right ≠ null)
      s.push(node.right)
    if (node.left ≠ null)
      s.push(node.left)

Правый потомок заносится первым, так что левый потомок обрабатывается первым

Через очередь:


levelorder(root)
  q ← empty queue
  q.enqueue(root)
  while (not q.isEmpty())
    node ← q.dequeue()
    visit(node)
    if (node.left ≠ null)
      q.enqueue(node.left)
    if (node.right ≠ null)
      q.enqueue(node.right)

Чтобы реализовать центрированный обход, не обязательно использовать рекурсии или стек. Для этого добавляют новые связи (полученное дерево будет называться прошитым бинарным деревом), где каждому левому потомку, у которого нет своего левого потомка, назначают указатель на предыдущий элемент в порядке центрированного обхода, а для правых по тем же причинам — следующий.

Прошитое бинарное дерево поиска

Типичная структура данных одного узла такого дерева выглядит так:


struct node {    
	data_type_t dat;    
	node *left, *right; //теперь left и right могут указывать как на дочерние элементы, так и содержать нитки, ведущие на другие уровни    
	bool left_is_thread, right_is_thread;
}

Другой способ обхода дерева заключается в способе хранения информации о связях в массиве. Такой способ позволяет быстро находить дочерние и родительские элементы, производя обычные арифметические операции (а именно — для левого потомка и для правого, где — индекс родительского узла, если считать с 1). Но эффективность заполнения такого массива напрямую зависит от полноты бинарного дерева. Самый худший вариант развития событий произойдёт тогда, когда у дерева есть только один дочерний элемент в каждом узле (не важно, левого или правого). Тогда для хранения узлов потребуется ячеек в массиве.

Использование обхода бинарных деревьев облегчает работу с алгебраическими выражениями. Так, обратная польская нотация для алгебраического выражения получается путём обратного обхода заранее построенного бинарного дерева. Такое дерево называется деревом синтаксического разбора выражения, в котором узлы хранят операнды (+, –, *, /), а листья — числовые значения.

Бинарное дерево на Go для новичка

Введение

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

Вставка узла.
Обход дерева.
Получение минимального и максимального элемента.

Что такое дерево?

Дерево — это структура данных, используемая для представления иерархии. Оно обычно состоит из нескольких небольших деревьев. Деревья представляют собой набор узлов, соединенных ребрами. Каждый узел содержит данные определенного типа. Бинарное дерево — это тип дерева, который по определению может иметь максимум два дочерних узла.

Дерево бинарного поиска

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

Зачем нужны бинарные деревья?

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

Предположим, что данные представлены в виде древовидной структуры. Тогда число шагов, необходимых для нахождения значения, уменьшается более чем наполовину: логарифмическая временная сложность O(logN). Это происходит потому, что всякий раз, когда значение вставляется в двоичное дерево поиска, добавление узла упорядоченно: значение левого дочернего элемента меньше значения родительского, а значение правого узла больше значения родительского узла.

Таким образом, когда мы ищем значение, если оно меньше корня, мы игнорируем всю правую часть дерева и рекурсивно повторяем поиск в левой части дерева.

Терминология

Узел. Каждый узел содержит указатели на левый и правый дочерний элемент и некоторые данные, связанные с узлом.
Лист — это узел без потомков.
Корень — самый верхний узел бинарного дерева.
Ребро связывает два узла вместе.

Дерево бинарного поиска на Go

Основное внимание в этой статье уделяется реализации бинарного дерева на Golang и нескольких функций для добавления или удаления узлов и т.д. Узел в Go может быть представлен как структура:

TreeNode struct {
 val   int
 left  *TreeNode
 right *TreeNode
}

Эта структура хранит значения int, но она может быть изменена для хранения других типов данных. Левое и правое поля в структуре указывают на другие узлы дерева.

Вставка узла в дерево

Это довольно просто: мы постоянно сравниваем значение вставляемого узла с узлами в двоичном дереве. Если значение вставляемых данных меньше, чем сравниваемый узел, и если левый потомок равен нулю, мы можем вставить новый узел как левый. Иначе мы сравниваем его с левым поддеревом и повторяем процесс.

(t *TreeNode) Insert(value int) error {
 if t == nil {
 return errors.New("Tree is nil")
 }

 if t.val == value {
 return errors.New("This node value already exists")
 }

 if t.val > value {
 if t.left == nil {
 t.left = &TreeNode{val: value}
 return nil
 }
 return t.left.Insert(value)
 }

 if t.val < value {
 if t.right == nil {
 t.right = &TreeNode{val: value}
 return nil
 }
 return t.right.Insert(value)
 }
 return nil
}

Каждая из этих функций принимает параметр.

Извлечение минимума

Эта функция рекурсивно находит минимальный элемент дерева:

(t *TreeNode) FindMin() int {
 if t.left == nil {
 return t.val
 }
 return t.left.FindMin()
}

Мы проверяем значения левых потомков, пока не достигнем nil.

Извлечение максимума

Эта функция находит максимальный элемент дерева. Подход тот же, но до достижения nil обходятся все правые потомки:

(t *TreeNode) FindMax() int {
 if t.right == nil {
 return t.val
 }
 return t.right.FindMax()
}

Обход бинарного дерева

В правильном дереве бинарного поиска обход всегда будет в порядке возрастания. Обход по порядку — это способ прохождения по двоичному дереву, при котором сначала идет левый дочерний элемент, затем родительский, а после — правый дочерний элемент узла. Код ниже показывает рекурсивный обход.

func (t *TreeNode) PrintInorder() {
 if t == nil {
 return
 }

 t.left.PrintInorder()
 fmt.Print(t.val)
 t.right.PrintInorder()
}

Заключение

Двоичные деревья поражают воображение, когда дело доходит до поиска данных, потому что в них он выполняется намного лучше, чем линейный поиск.

Правильное двоичное дерево будет иметь значение левого потомка меньше корня, а значение правого потомка больше корня.

Полный код с большим количеством других функций доступен по адресу https://github.com/puneeth8994/binary-tree-go-impl.

«Меня только что попросили сбалансировать двоичное дерево поиска в аэропорту» Статьи редакции

При въезде в США инженеру-программисту пришлось проходить тест, чтобы доказать, что он инженер-программист.

{«id»:41543,»url»:»https:\/\/tjournal.ru\/flood\/41543-menya-tolko-chto-poprosili-sbalansirovat-dvoichnoe-derevo-poiska-v-aeroportu»,»title»:»\u00ab\u041c\u0435\u043d\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0447\u0442\u043e \u043f\u043e\u043f\u0440\u043e\u0441\u0438\u043b\u0438 \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0430\u044d\u0440\u043e\u043f\u043e\u0440\u0442\u0443\u00bb»,»services»:{«vkontakte»:{«url»:»https:\/\/vk.com\/share.php?url=https:\/\/tjournal.ru\/flood\/41543-menya-tolko-chto-poprosili-sbalansirovat-dvoichnoe-derevo-poiska-v-aeroportu&title=\u00ab\u041c\u0435\u043d\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0447\u0442\u043e \u043f\u043e\u043f\u0440\u043e\u0441\u0438\u043b\u0438 \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0430\u044d\u0440\u043e\u043f\u043e\u0440\u0442\u0443\u00bb»,»short_name»:»VK»,»title»:»\u0412\u041a\u043e\u043d\u0442\u0430\u043a\u0442\u0435″,»width»:600,»height»:450},»facebook»:{«url»:»https:\/\/www.facebook.com\/sharer\/sharer.php?u=https:\/\/tjournal.ru\/flood\/41543-menya-tolko-chto-poprosili-sbalansirovat-dvoichnoe-derevo-poiska-v-aeroportu»,»short_name»:»FB»,»title»:»Facebook»,»width»:600,»height»:450},»twitter»:{«url»:»https:\/\/twitter.com\/intent\/tweet?url=https:\/\/tjournal.ru\/flood\/41543-menya-tolko-chto-poprosili-sbalansirovat-dvoichnoe-derevo-poiska-v-aeroportu&text=\u00ab\u041c\u0435\u043d\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0447\u0442\u043e \u043f\u043e\u043f\u0440\u043e\u0441\u0438\u043b\u0438 \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0430\u044d\u0440\u043e\u043f\u043e\u0440\u0442\u0443\u00bb»,»short_name»:»TW»,»title»:»Twitter»,»width»:600,»height»:450},»telegram»:{«url»:»tg:\/\/msg_url?url=https:\/\/tjournal.ru\/flood\/41543-menya-tolko-chto-poprosili-sbalansirovat-dvoichnoe-derevo-poiska-v-aeroportu&text=\u00ab\u041c\u0435\u043d\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0447\u0442\u043e \u043f\u043e\u043f\u0440\u043e\u0441\u0438\u043b\u0438 \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0430\u044d\u0440\u043e\u043f\u043e\u0440\u0442\u0443\u00bb»,»short_name»:»TG»,»title»:»Telegram»,»width»:600,»height»:450},»odnoklassniki»:{«url»:»http:\/\/connect.ok.ru\/dk?st.cmd=WidgetSharePreview&service=odnoklassniki&st.shareUrl=https:\/\/tjournal.ru\/flood\/41543-menya-tolko-chto-poprosili-sbalansirovat-dvoichnoe-derevo-poiska-v-aeroportu»,»short_name»:»OK»,»title»:»\u041e\u0434\u043d\u043e\u043a\u043b\u0430\u0441\u0441\u043d\u0438\u043a\u0438″,»width»:600,»height»:450},»email»:{«url»:»mailto:?subject=\u00ab\u041c\u0435\u043d\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0447\u0442\u043e \u043f\u043e\u043f\u0440\u043e\u0441\u0438\u043b\u0438 \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0430\u044d\u0440\u043e\u043f\u043e\u0440\u0442\u0443\u00bb&body=https:\/\/tjournal.ru\/flood\/41543-menya-tolko-chto-poprosili-sbalansirovat-dvoichnoe-derevo-poiska-v-aeroportu»,»short_name»:»Email»,»title»:»\u041e\u0442\u043f\u0440\u0430\u0432\u0438\u0442\u044c \u043d\u0430 \u043f\u043e\u0447\u0442\u0443″,»width»:600,»height»:450}},»isFavorited»:false}

51 855

просмотров

26 февраля африканский инженер-программист Целестин Омин (Celestine Omin) по работе отправился из Нигерии в Нью-Йорк, однако после прибытия в аэропорт столкнулся с неожиданной проблемой. Сотрудники таможенной и пограничной службы США не поверили, что он указал свою настоящую профессию, и предложили ему решить несколько заданий в качестве доказательства своей компетенции. Об этом сообщается в редакторском разделе LinkedIn Pulse.

Целестин Омин

По словам Омина, он впервые посетил Америку. За несколько месяцев до этого он стал старшим техническим консультантом в стартапе Andela, помогающим талантливым африканским программистам найти работодателей в США. В феврале Омин получил кратковременную американскую визу и отправился в Нью-Йорк, чтобы помочь местному сервису First Access.

После 24-часового полёта самолёт с сотрудником Andela на борту приземлился в Международном аэропорту имени Джона Кеннеди, однако после этого Омин не смог пройти таможенный осмотр. По его словам, офицер задал ему несколько вопросов о целях визита и работе, после чего пригласил пройти в отдельную комнату.

Примерно через час в комнату зашёл второй сотрудник, который начал спрашивать, правильно ли указано в визе, что Омин работает инженером-программистом. Когда африканец подтвердил информацию, офицер дал ему ручку и бумагу, предложив доказать свою профессию ответами на тест.

Таможенная и пограничная служба США составила для Омина два вопроса: «Расскажите, как проверить, является ли двоичное дерево поиска сбалансированным» и «Что такое абстрактный класс, и зачем он нужен?».

I was just asked to balance a Binary Search Tree by JFK’s airport immigration. Welcome to America.

«Меня только что попросили сбалансировать двоичное дерево поиска в аэропорту. Добро пожаловать в Америку»

Омин, работающий инженером-программистом уже семь лет, отметил, что вопросы были составлены так, будто офицеры искали в Google «Вопросы, которые можно спросить у инженера-программиста». По его словам, он очень устал за время перелёта и ожидания офицеров, но постарался выполнить задания. Через 10 минут он передал ответы, однако сотрудники таможни заявили, что они неправильные.

Омин в разговоре с LinkedIn подчеркнул, что «технически» он ответил верно, а у офицеров просто не было достаточных знаний, чтобы его понять.

@ssharwood sad thing is, if I didn’t give the Wikipedia definition for these questions, it was considered a wrong answer.

«К сожалению, то, что я не дал определение из Википедии, они расценили как неправильный ответ»

Позже Омина всё-таки отпустили. При этом допрашивающий его офицер на прощание заявил, что он его «не убедил». Омин узнал, что таможенная служба разрешила ему въехать в страну только после звонков в Andela и First Access. Сооснователь африканского стартапа Кристина Сасс (Christina Sass) подтвердила эту информацию LinkedIn. Редактор сервиса обратилась за комментарием в таможенную и пограничную службу США, но не получила ответа.

В конце февраля СМИ сообщили, что в американском аэропорту за «звучащие по-арабски имена» задержали сына Мохаммеда Али — Мохаммеда Али младшего. Однако блог Powerline усомнился в правдивости этой истории.

VisuAlgo — Двоичное Поисковое Дерево, АВЛ-дерево

A Binary Search Tree (BST) is a binary tree in which each vertex has only up to 2 children that satisfies BST property: All vertices in the left subtree of a vertex must hold a value smaller than its own and all vertices in the right subtree of a vertex must hold a value larger than its own (we have assumption that all values are distinct integers in this visualization and small tweak is needed to cater for duplicates/non integer). Try clicking Search(7) for a sample animation on searching a random value &in; [1..99] in the random BST above.

An Adelson-Velskii Landis (AVL) tree is a self-balancing BST that maintains it’s height to be O(log N) when having N vertices in the AVL tree.

Click ‘Next’ (on the top right)/press ‘Page Down’ to advance this e-Lecture slide, use the drop down list/press ‘Space’ to jump to a specific slide, or Click ‘X’ (on the bottom right)/press ‘Esc’ to go to Exploration mode.

Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
Please login if you are a repeated visitor or register for an (optional) free account first.

1. Binary Search Tree2. BST & Balanced BST (AVL Tree)3. Motivation 3-1. What Kind of Table ADT? 3-2. Using Unsorted Array/Vector 3-3. Using Sorted Array/Vector 3-4. O(log N) Complexities? 3-5. Other Table ADT Operations 3-6. The Solution 3-7. What about Linked List? 3-8. The Solution 3-9. What about Hash Table? 3-10. The Solution4. Visualization 4-1. BST Vertex Attributes 4-2. BST Property5. BST Operations 5-1. A Few Other BST Operations 5-2. Static vs Dynamic Data Structure6. Search(v) 6-1. FindMin() and FindMax() 6-2. O(h) Time Complexity7. Successor(v) 7-1. Predecessor(v) 7-2. O(h) Time Complexity8. Inorder Traversal 8-1. O(N) Time Complexity 8-2. The Solution 8-3. Preorder and Postorder Traversal9. Insert(v) 9-1. O(h) Time Complexity 9-2. Mini Quiz10. Remove(v) — Three Possible Cases 10-1. Remove(v) — Case 1 10-2. Remove(v) — Case 2 10-3. Remove(v) — Case 3 10-4. Remove(v) — Case 3 Discussion 10-5. The Answer 10-6. O(h) Time Complexity11. Create BST12. Intermezzo 12-1. Try Exploration Mode13. Balanced BST 13-1. AVL Tree 13-2. Extra BST Attribute: height(v) 13-3. Formal Definition of height(v) 13-4. Mini Quiz 13-5. The Lower Bound of BST Height 13-6. Derivation of the Lower Bound 13-7. The Upper Bound of BST Height 13-8. The Solution 13-9. The Combined Bound14. AVL Tree 14-1. Step 1: Maintaining height(v) Efficiently 14-2. Step 2: Define AVL Tree Invariant 14-3. Proof — 1 14-4. Proof — 2 14-5. Proof — 3 14-6. Proof — 4 14-7. Step 3: Maintain Invariant 14-8. Introducing Tree Rotation 14-9. Non-trivial O(1) Tree Rotation Pseudo-code 14-10. Four Rebalancing Cases 14-11. Insert(v) in AVL Tree 14-12. The Answer 14-13. Remove(v) in AVL Tree 14-14. AVL Tree Summary15. Extras 15-1. Those 2 Extra BST Operations 15-2. Side Usage of Balanced BST? 15-3. Online Quiz 15-4. Online Judge Exercises 15-5. The Solution99. Status Panel 99-1. Codetrace Panel 99-2. Media Control 99-3. Return to ‘Exploration Mode’

X Esc

Вперед PgDn

To toggle between the standard Binary Search Tree and the AVL Tree (only different behavior during Insertion and Removal of an Integer), select the respective header.

We also have URL shortcut to quickly access the AVL Tree mode, which is https://visualgo.net/en/avl (you can change the ‘en’ to your two characters preferred language — if available).

Pro-tip: Since you are not logged-in, you may be a first time visitor who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown] to advance to the next slide, [PageUp] to go back to the previous slide, [Esc] to toggle between this e-Lecture mode and exploration mode.

X Esc

Назад PgUp

Вперед PgDn

BST (and especially balanced BST like AVL Tree) is an efficient data structure to implement a certain kind of Table (or Map) Abstract Data Type (ADT).

A Table ADT must support at least the following three operations as efficient as possible:

Search(v) — determine if v exists in the ADT or not,
Insert(v) — insert v into the ADT,
Remove(v) — remove v from the ADT.

Reference: See similar slide in Hash Table e-Lecture.

Another pro-tip: We designed this visualization and this e-Lecture mode to look good on 1366×768 resolution or larger (typical modern laptop resolution in 2017). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl —) to calibrate this.

X Esc

Назад PgUp

Вперед PgDn

We are referring to Table ADT where the keys need to be ordered (as opposed to Table ADT where the keys do not need to be unordered).

This special requirement of Table ADT will be made clearer in the next few slides.

X Esc

Назад PgUp

Вперед PgDn

If we use unsorted array/vector to implement Table ADT, it can be inefficient:

Search(v) runs in O(N), as we may end up exploring all N elements of the ADT if v actually does not exist,
Insert(v) can be implemented in O(1), just put v at the back of the array,
Remove(v) runs in O(N) too as we have to first search for v which is already O(N) and later close the resulting gap after deletion — also in O(N).

X Esc

Назад PgUp

Вперед PgDn

If we use sorted array/vector to implement Table ADT, we can improve the Search(v) performance but weakens the Insert(v) performance:

Search(v) can now be implemented in O(log N), as we can now use binary search on the sorted array,
Insert(v) now runs in O(N) as we need to implement an insertion-sort like strategy to make the array remains sorted,
Remove(v) runs in O(N) because even if Search(v) runs in O(log N), we still need to close the gap after deletion — which is in O(N).

X Esc

Назад PgUp

Вперед PgDn

The goal for this e-Lecture is to introduce BST and then balanced BST (AVL Tree) data structure so that we can implement the basic Table ADT operations: Search(v), Insert(v), Remove(v), and a few other Table ADT operations — see the next slide — in O(log N) time — which is much smaller than N.

PS: Some of the more experienced readers may notice that ∃ another data structure that can implement the three basic Table ADT operations in faster time, but read on…

N	≈ 1 000	≈ 1 000 000	≈ 1 000 000 000
log N	10	Only 20 :O	Only 30 :O:O

X Esc

Назад PgUp

Вперед PgDn

On top of the basic three, there are a few other possible Table ADT operations:

Find the Min()/Max() element,
Find the Successor(v) — ‘next larger’/Predecessor(v) — ‘previous smaller’ element,
List elements in sorted order,
Operation X & Y — hidden for pedagogical purpose in an NUS module,
There are others possible operations.

Discussion: What are the best possible implementation for the first three additional operations if we are limited to use [sorted|unsorted] array/vector?

X Esc

Назад PgUp

Вперед PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc

Назад PgUp

Вперед PgDn

The simpler data structure that can be used to implement Table ADT is Linked List.

Quiz: Can we perform all basic three Table ADT operations: Search(v)/Insert(v)/Remove(v) efficiently (read: faster than O(N)) using Linked List?

Submit

Discussion: Why?

X Esc

Назад PgUp

Вперед PgDn

X Esc

Назад PgUp

Вперед PgDn

Another data structure that can be used to implement Table ADT is Hash Table. It has very fast Search(v), Insert(v), and Remove(v) performance (all in expected O(1) time).

Quiz: So what is the point of learning this BST module if Hash Table can do the crucial Table ADT operations in unlikely-to-be-beaten expected O(1) time?

Submit

Discuss the answer above! Hint: Go back to the previous 4 slides ago.

X Esc

Назад PgUp

Вперед PgDn

X Esc

Назад PgUp

Вперед PgDn

We will now introduce BST data structure. See the visualization of an example BST above!

Root vertex does not have a parent. There can only be one root vertex in a BST. Leaf vertex does not have any child. There can be more than one leaf vertex in a BST. Vertices that are not leaf are called the internal vertices. Sometimes root vertex is not included as part of the definition of internal vertex as the root of a BST with only one vertex can actually fit into the definition of a leaf too.

In the example above, vertex 15 is the root vertex, vertex {5, 7, 50} are the leaves, vertex {4, 6, 15 (also the root), 23, 71} are the internal vertices.

X Esc

Назад PgUp

Вперед PgDn

Each vertex has at least 4 attributes: parent, left, right, key/value/data (there are potential other attributes). Not all attributes will be used for all vertices, e.g. the root vertex will have its parent attribute = NULL. Some other implementation separates key (for ordering of vertices in the BST) with the actual satellite data associated with the keys.

The left/right child of a vertex (except leaf) is drawn on the left/right and below of that vertex, respectively. The parent of a vertex (except root) is drawn above that vertex. The (integer) key of each vertex is drawn inside the circle that represent that vertex. In the example above, (key) 15 has 6 as its left child and 23 as its right child. Thus the parent of 6 (and 23) is 15.

X Esc

Назад PgUp

Вперед PgDn

As we do not allow duplicate integer in this visualization, the BST property is as follow: For every vertex X, all vertices on the left subtree of X are strictly smaller than X and all vertices on the right subtree of X are strictly greater than X.

In the example above, the vertices on the left subtree of the root 15: {4, 5, 6, 7} are all smaller than 15 and the vertices on the right subtree of the root 15: {23, 50, 71} are all greater than 15. You can recursively check BST property on other vertices too.

For more complete implementation, we should consider duplicate integers too and we must consistently place integers that are equal to X to one subtree only (not arbitrary).

X Esc

Назад PgUp

Вперед PgDn

We provide visualization for the following common BST/AVL Tree operations:

Query operations (the BST structure remains unchanged):
1. Search(v),
2. Predecessor(v) (and similarly Successor(v)), and
3. Inorder Traversal (we will add Preorder and Postorder Traversal soon),
Update operations (the BST structure may likely change):
1. Insert(v),
2. Remove(v), and
3. Create BST (several criteria).

X Esc

Назад PgUp

Вперед PgDn

There are a few other BST (Query) operations that have not been visualized in VisuAlgo:

Rank(v): Given a key v, determine what is its rank (1-based index) in the sorted order of the BST elements. That is, Rank(FindMin()) = 1 and Rank(FindMax()) = N. If v does not exist, we can report -1.
Select(k): Given a rank k, 1 ≤ k ≤ N, determine the key v that has that rank k in the BST. Or in another word, find the k-th smallest element in the BST. That is, Select(1) = FindMin() and Select(N) = FindMax().

The details of these two operations are currently hidden for pedagogical purpose in a certain NUS module.

X Esc

Назад PgUp

Вперед PgDn

Data structure that is only efficient if there is no (or rare) update, especially the insert and/or remove operation(s) is called static data structure.

Data structure that is efficient even if there are many update operations is called dynamic data structure. BST and especially balanced BST (e.g. AVL Tree) are in this category.

X Esc

Назад PgUp

Вперед PgDn

Because of the way data (distinct integers for this visualization) is organised inside a BST, we can binary search for an integer v efficiently (hence the name of Binary Search Tree).

First, we set the current vertex = root and then check if the current vertex is smaller/equal/larger than integer v that we are searching for. We then go to the right subtree/stop/go the left subtree, respectively. We keep doing this until we either find the required vertex or we don’t.

On the example BST above, try clicking Search(15) (found after just 1 comparison), Search(7) (found after 3 comparisons), Search(21) (not found after 3 comparisons).

X Esc

Назад PgUp

Вперед PgDn

Similarly, because of the way data is organised inside a BST, we can find the minimum/maximum element (an integer in this visualization) by starting from root and keep going to the left/right subtree, respectively.

Try clicking FindMin() and FindMax() on the example BST shown above. The answers should be 4 and 71 (both after 4 comparisons).

X Esc

Назад PgUp

Вперед PgDn

Search(v)/FindMin()/FindMax() operations run in O(h) where h is the height of the BST.

But note that this h can be as tall as O(N) in a normal BST as shown in the random ‘skewed right’ example above. Try Search(100) (this value should not exist as we only use random integers between [1..99] to generate this random BST and thus the Search routine should check all the way from root to the only leaf in O(N) time — not efficient.

X Esc

Назад PgUp

Вперед PgDn

Because of the BST properties, we can find the Successor of an integer v (assume that we already know where integer v is located from earlier call of Search(v)) as follows:

If v has a right subtree, the minimum integer in the right subtree of v must be the successor of v. Try Successor(23) (should be 50).
If v does not have a right subtree, we need to traverse the ancestor(s) of v until we find ‘a right turn’ to vertex w (or alternatively, until we find the first vertex w that is greater than vertex v). Once we find vertex w, we will see that vertex v is the maximum element in the left subtree of w. Try Successor(7) (should be 15).
If v is the maximum integer in the BST, v does not have a successor. Try Successor(71) (should be none).

X Esc

Назад PgUp

Вперед PgDn

The operations for Predecessor of an integer v are defined similarly (just the mirror of Successor operations).

Try the same three corner cases (but mirrored): Predecessor(6) (should be 5), Predecessor(50) (should be 23), Predecessor(4) (should be none).

At this point, stop and ponder these three Successor(v)/Predecessor(v) cases to ensure that you understand these concepts.

X Esc

Назад PgUp

Вперед PgDn

Predecessor(v) and Successor(v) operations run in O(h) where h is the height of the BST.

But recall that this h can be as tall as O(N) in a normal BST as shown in the random ‘skewed right’ example above. If we call Successor(FindMax()), we will go up from that last leaf back to the root in O(N) time — not efficient.

X Esc

Назад PgUp

Вперед PgDn

We can perform an Inorder Traversal of this BST to obtain a list of sorted integers inside this BST (in fact, if we ‘flatten’ the BST into one line, we will see that the vertices are ordered from smallest/leftmost to largest/rightmost).

Inorder Traversal is a recursive method whereby we visit the left subtree first, exhausts all items in the left subtree, visit the current root, before exploring the right subtree and all items in the right subtree. Without further ado, let’s try Inorder Traversal to see it in action on the example BST above.

X Esc

Назад PgUp

Вперед PgDn

Inorder Traversal runs in O(N), regardless of the height of the BST.

Discussion: Why?

PS: Some people call insertion of N unordered integers into a BST in O(N log N) and then performing the O(N) Inorder Traversal as ‘BST sort‘. It is rarely used though as there are several easier-to-use (comparison-based) sorting algorithms than this.

X Esc

Назад PgUp

Вперед PgDn

X Esc

Назад PgUp

Вперед PgDn

We have not included the animation of these two other classic tree traversal methods, but we will do so very soon.

But basically, in Preorder Traversal, we visit the current root before going to left subtree and then right subtree. For the example BST shown in the background, we have: {{15}, {6, 4, 5, 7}, {23, 71, 50}}. PS: Do you notice the recursive pattern? root, members of left subtree of root, members of right subtree of root.

In Postorder Traversal, we visit the left subtree and right subtree first, before visiting the current root. For the example BST shown in the background, we have: {{5, 4, 7, 6}, {50, 71, 23}, {15}}.

X Esc

Назад PgUp

Вперед PgDn

We can insert a new integer into BST by doing similar operation as Search(v). But this time, instead of reporting that the new integer is not found, we create a new vertex in the insertion point and put the new integer there. Try Insert(60) on the example above.

X Esc

Назад PgUp

Вперед PgDn

Insert(v) runs in O(h) where h is the height of the BST.

By now you should be aware that this h can be as tall as O(N) in a normal BST as shown in the random ‘skewed right’ example above. If we call Insert(FindMax()+1), i.e. we insert a new integer greater than the current max, we will go from root down to the last leaf and then insert the new integer as the right child of that last leaf in O(N) time — not efficient (note that we only allow up to h=9 in this visualization).

X Esc

Назад PgUp

Вперед PgDn

Quiz: Inserting integers [1,10,2,9,3,8,4,7,5,6] one by one in that order into an initially empty BST will result in a BST of height:

Submit

Pro-tip: You can use the ‘Exploration mode’ to verify the answer.

X Esc

Назад PgUp

Вперед PgDn

We can remove an integer in BST by performing similar operation as Search(v).

If v is not found in the BST, we simply do nothing.

If v is found in the BST, we do not report that the existing integer v is found, but instead, we perform one of the three possible removal cases that will be elaborated in three separate slides (we suggest that you try each of them one by one).

X Esc

Назад PgUp

Вперед PgDn

The first case is the easiest: Vertex v is currently one of the leaf vertex of the BST.

Deletion of a leaf vertex is very easy: We just remove that leaf vertex — try Remove(5) on the example BST above (second click onwards after the first removal will do nothing — please refresh this page or go to another slide and return to this slide instead).

This part is clearly O(1) — on top of the earlier O(h) search-like effort.

X Esc

Назад PgUp

Вперед PgDn

The second case is also not that hard: Vertex v is an (internal/root) vertex of the BST and it has exactly one child. Removing v without doing anything else will disconnect the BST.

Deletion of a vertex with one child is not that hard: We connect that vertex’s only child with that vertex’s parent — try Remove(23) on the example BST above (second click onwards after the first removal will do nothing — please refresh this page or go to another slide and return to this slide instead).

This part is also clearly O(1) — on top of the earlier O(h) search-like effort.

X Esc

Назад PgUp

Вперед PgDn

The third case is the most complex among the three: Vertex v is an (internal/root) vertex of the BST and it has exactly two children. Removing v without doing anything else will disconnect the BST.

Deletion of a vertex with two children is as follow: We replace that vertex with its successor, and then delete its duplicated successor in its right subtree — try Remove(6) on the example BST above (second click onwards after the first removal will do nothing — please refresh this page or go to another slide and return to this slide instead).

This part requires O(h) due to the need to find the successor vertex — on top of the earlier O(h) search-like effort.

X Esc

Назад PgUp

Вперед PgDn

This case 3 warrants further discussions:

Why replacing a vertex B that has two children with its successor C is always a valid strategy?
Can we replace vertex B that has two children with its predecessor A instead? Why or why not?

X Esc

Назад PgUp

Вперед PgDn

X Esc

Назад PgUp

Вперед PgDn

Remove(v) runs in O(h) where h is the height of the BST. Removal case 3 (deletion of a vertex with two children is the ‘heaviest’ but it is not more than O(h)).

As you should have fully understand by now, h can be as tall as O(N) in a normal BST as shown in the random ‘skewed right’ example above. If we call Remove(FindMax()), i.e. we remove the current max integer, we will go from root down to the last leaf in O(N) time before removing it — not efficient.

X Esc

Назад PgUp

Вперед PgDn

To make life easier in ‘Exploration Mode’, you can create a new BST using these options:

Empty BST (you can then insert a few integers one by one),
The two e-Lecture Examples that you may have seen several times so far,
Random BST (which unlikely to be extremely tall),
Skewed Left/Right BST (tall BST with N vertices and N-1 linked-list like edges, to showcase the worst case behavior of BST operations; disabled in AVL Tree mode).

X Esc

Назад PgUp

Вперед PgDn

We are midway through the explanation of this BST module. So far we notice that many basic Table ADT operations run in O(h) and h can be as tall as N-1 edges like the ‘skewed left’ example shown — inefficient :(…

So, is there a way to make our BSTs ‘not that tall’?

PS: If you want to study how these basic BST operations are implemented in a real program, you can download this BSTDemo.cpp.

X Esc

Назад PgUp

Вперед PgDn

At this point, we encourage you to press [Esc] or click the X button on the bottom right of this e-Lecture slide to enter the ‘Exploration Mode’ and try various BST operations yourself to strengthen your understanding about this versatile data structure.

When you are ready to continue with the explanation of balanced BST (we use AVL Tree as our example), press [Esc] again or switch the mode back to ‘e-Lecture Mode’ from the top-right corner drop down menu. Then, use the slide selector drop down list to resume from this slide 12-1.

X Esc

Назад PgUp

Вперед PgDn

We have seen from earlier slides that most of our BST operations except Inorder traversal runs in O(h) where h is the height of the BST that can be as tall as N-1.

We will continue our discussion with the concept of balanced BST so that h = O(log N).

X Esc

Назад PgUp

Вперед PgDn

There are several known implementations of balanced BST, too many to be visualized and explained one by one in VisuAlgo.

We focus on AVL Tree (Adelson-Velskii & Landis, 1962) that is named after its inventor: Adelson-Velskii and Landis.

Other balanced BST implementations (more or less as good or slightly better in terms of constant-factor performance) are: Red-Black Tree, B-trees/2-3-4 Tree (Bayer & McCreight, 1972), Splay Tree (Sleator and Tarjan, 1985), Skip Lists (Pugh, 1989), Treaps (Seidel and Aragon, 1996), etc.

X Esc

Назад PgUp

Вперед PgDn

To facilitate AVL Tree implementation, we need to augment — add more information/attribute to — each BST vertex.

For each vertex v, we define height(v): The number of edges on the path from vertex v down to its deepest leaf. This attribute is saved in each vertex so we can access a vertex’s height in O(1) without having to recompute it every time.

X Esc

Назад PgUp

Вперед PgDn

Formally:

v.height = -1 (if v is an empty tree)
v.height = max(v.left.height, v.right.height) + 1 (otherwise)

The height of the BST is thus: root.height.

On the example BST above, height(11) = height(32) = height(50) = height(72) = height(99) = 0 (all are leaves). height(29) = 1 as there is 1 edge connecting it to its only leaf 32.

X Esc

Назад PgUp

Вперед PgDn

If we have N elements/items/keys in our BST, the lower bound height h > log₂N if we can somehow insert the N elements in perfect order so that the BST is perfectly balanced.

See the example shown above for N = 15 (a perfect BST which is rarely achievable in real life — try inserting any other integer and it will not be perfect anymore).

X Esc

Назад PgUp

Вперед PgDn

N ≤ 1 + 2 + 4 + ... + 2^h
N ≤ 2⁰ + 2¹ + 2² + … + 2^h
N < 2^h+1 (sum of geometric progression)
log₂ N < log₂ 2^h+1
log₂ N < (h+1) * log₂ 2 (log₂ 2 is 1)
h > (log₂ N)-1 (algebraic manipulation)
h > log₂ N

X Esc

Назад PgUp

Вперед PgDn

If we have N elements/items/keys in our BST, the upper bound height h < N if we insert the elements in ascending order (to get skewed right BST as shown above).

The height of such BST is h = N-1, so we have h < N.

Discussion: Do you know how to get skewed left BST instead?

X Esc

Назад PgUp

Вперед PgDn

X Esc

Назад PgUp

Вперед PgDn

We have seen that most BST operations are in O(h) and combining the lower and upper bounds of h, we have log₂N < h < N.

There is a dramatic difference between log₂N and N and we have seen from the discussion of the lower bound that getting perfect BST (at all times) is near impossible…

So can we have BST that has height closer to log₂N, i.e. c * log₂N, for a small constant factor c? If we can, then BST operations that run in O(h) actually run in O(log N)…

X Esc

Назад PgUp

Вперед PgDn

Introducing AVL Tree, invented by two Russian (Soviet) inventors: Georgy Adelson-Velskii and Evgenii Landis, back in 1962.

In AVL Tree, we will later see that its height h < 2 * log N (tighter analysis exist, but we will use easier analysis in VisuAlgo where c = 2). Therefore, most AVL Tree operations run in O(log N) time — efficient.

Insert(v) and Remove(v) update operations may change the height h of the AVL Tree, but we will see rotation operation(s) to maintain the AVL Tree height to be low.

X Esc

Назад PgUp

Вперед PgDn

To have efficient performance, we shall not maintain height(v) attribute via the O(N) recursive method every time there is an update (Insert(v)/Remove(v)) operation.

Instead, we compute O(1): x.height = max(x.left.height, x.right.height) + 1 at the back of our Insert(v)/Remove(v) operation as only the height of vertices along the insertion/removal path may be affected. Thus, only O(h) vertices may change its height(v) attribute and in AVL Tree, h < 2 * log N.

Try Insert(37) on the example AVL Tree (ignore the resulting rotation for now, we will come back to it in the next few slides). Notice that only a few vertices along the insertion path: {41,20,29,32} increases their height by +1 and all other vertices will have their heights unchanged.

X Esc

Назад PgUp

Вперед PgDn

Let’s define the following important AVL Tree invariant (property that will never change): A vertex v is said to be height-balanced if |v.left.height — v.right.height| ≤ 1.

A BST is called height-balanced according to the invariant above if every vertex in the BST is height-balanced. Such BST is called AVL Tree, like the example shown above.

Take a moment to pause here and try inserting a few new random vertices or deleting a few random existing vertices. Will the resulting BST still considered height-balanced?

X Esc

Назад PgUp

Вперед PgDn

Adelson-Velskii and Landis claim that an AVL Tree (a height-balanced BST that satisfies AVL Tree invariant) with N vertices has height h < 2 * log₂N.

The proof relies on the concept of minimum-size AVL Tree of a certain height h.

Let N_h be the minimum number of vertices in a height-balanced AVL Tree of height h.

The first few values of N_h are N₀ = 1 (a single root vertex), N₁ = 2 (a root vertex with either one left child or one right child only), N₂ = 4, N₃ = 7, N₄ = 12, N₅ = 20 (see the background picture), and so on (see the next two slides).

X Esc

Назад PgUp

Вперед PgDn

We know that for any other AVL Tree of N vertices (not necessarily the minimum-size one), we have N ≥ N_h.

In the background picture, we have N₅ = 20 vertices but we know that we can squeeze 43 more vertices (up to N = 63) before we have a perfect binary tree of height h = 5.

X Esc

Назад PgUp

Вперед PgDn

N_h = 1 + N_h-1 + N_h-2 (formula for minimum-size AVL tree of height h)
N_h > 1 + 2*N_h-2 (as N_h-1 > N_h-2)
N_h > 2*N_h-2 (obviously)
N_h > 4*N_h-4 (recursive)
N_h > 8*N_h-6 (another recursive step)
... (we can only do this h/2 times, assuming initial h is even)
N_h > 2^h/2*N₀ (we reach base case)
N_h > 2^h/2 (as N₀ = 1)

X Esc

Назад PgUp

Вперед PgDn

N ≥ N_h > 2^h/2 (combining the previous two slides)
N > 2^h/2
log₂(N) > log₂(2^h/2) (log₂ on both sides)
log₂(N) > h/2 (formula simplification)
2 * log₂(N) > h or h < 2 * log₂(N)
h = O(log(N)) (the final conclusion)

X Esc

Назад PgUp

Вперед PgDn

Look at the example BST again. See that all vertices are height-balanced, an AVL Tree.

To quickly detect if a vertex v is height balanced or not, we modify the AVL Tree invariant (that has absolute function inside) into: bf(v) = v.left.height — v.right.height.

Now try Insert(37) on the example AVL Tree again. A few vertices along the insertion path: {41,20,29,32} increases their height by +1. Vertices {29,20} will no longer be height-balanced after this insertion (and will be rotated later — discussed in the next few slides), i.e. bf(29) = -2 and bf(20) = -2 too. We need to restore the balance.

X Esc

Назад PgUp

Вперед PgDn

See the picture above. Calling rotateRight(Q) on the left picture will produce the right picture. Calling rotateLeft(P) on the right picture will produce the left picture again.

rotateRight(T)/rotateLeft(T) can only be called if T has a left/right child, respectively.

Tree Rotation preserves BST property. Before rotation, P ≤ B ≤ Q. After rotation, notice that subtree rooted at B (if it exists) changes parent, but P ≤ B ≤ Q does not change.

X Esc

Назад PgUp

Вперед PgDn

BSTVertex rotateLeft(BSTVertex T) // pre-req: T.right != null
BSTVertex w = T.right // rotateRight is the mirror copy of this
w.parent = T.parent // this method is hard to get right for newbie
T.parent = w
T.right = w.left
if (w.left != null) w.left.parent = T
w.left = T
// update the height of T and then w here
return w

X Esc

Назад PgUp

Вперед PgDn

Basically, there are only these four imbalance cases. We use Tree Rotation(s) to deal with each of them.

X Esc

Назад PgUp

Вперед PgDn

Just insert v as in normal BST,
Walk up the AVL Tree from the insertion point back to the root and at every step, we update the height and balance factor of the affected vertices:
1. Stop at the first vertex that is out-of-balance (+2 or -2), if any,
2. Use one of the four tree rotation cases to rebalance it again, e.g. try Insert(37) on the example above and notice by calling rotateLeft(29) once, we fix the imbalance issue.

Discussion: Is there other tree rotation cases for Insert(v) operation of AVL Tree?

X Esc

Назад PgUp

Вперед PgDn

X Esc

Назад PgUp

Вперед PgDn

Just remove v as in normal BST (one of the three removal cases),
Walk up the AVL Tree from the deletion point back to the root and at every step, we update the height and balance factor of the affected vertices:
1. Now for every vertex that is out-of-balance (+2 or -2), we use one of the four tree rotation cases to rebalance them (can be more than one) again.

The main difference compared to Insert(v) in AVL tree is that we may trigger one of the four possible rebalancing cases several times, but not more than h = O(log N) times :O, try Remove(7) on the example above to see two chain reactions rotateRight(6) and then rotateRight(16)+rotateLeft(8) combo.

X Esc

Назад PgUp

Вперед PgDn

X Esc

Назад PgUp

Вперед PgDn

We will end this module with a few more interesting things about BST and balanced BST (especially AVL Tree).

X Esc

Назад PgUp

Вперед PgDn

X Esc

Назад PgUp

Вперед PgDn

X Esc

Назад PgUp

Вперед PgDn

For a few more interesting questions about this data structure, please practice on BST/AVL training module (no login is required).

However, for registered users, you should login and then go to the Main Training Page to officially clear this module and such achievement will be recorded in your user account.

X Esc

Назад PgUp

Вперед PgDn

We also have a few programming problems that somewhat requires the usage of this balanced BST (like AVL Tree) data structure: Kattis — compoundwords and Kattis — baconeggsandspam.

Try them to consolidate and improve your understanding about this data structure. You are allowed to use C++ STL map/set, Java TreeMap/TreeSet, or OCaml Map/Set if that simplifies your implementation (Note that Python doesn’t have built-in bBST implementation).

X Esc

Назад PgUp

Вперед PgDn

X Esc

Назад PgUp

Вперед PgDn

As the action is being carried out, each step will be described in the status panel.

X Esc

Назад PgUp

Вперед PgDn

X Esc

Назад PgUp

Вперед PgDn

Control the animation with the player controls! Keyboard shortcuts are:

Spacebar: play/pause/replay

Left/right arrows: step backward/step forward
-/+: decrease/increase speed

X Esc

Назад PgUp

Вперед PgDn

Return to ‘Exploration Mode’ to start exploring!

Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.

X Esc

Назад PgUp

Создать

Найти
(v)

Вставить(v)

Удалить(v)

Предшественник/преемник(v)

Tree Traversal

О нас

VisuAlgo was conceptualised in 2011 by Dr Steven Halim as a tool to help his students better understand data structures and algorithms, by allowing them to learn the basics on their own and at their own pace.

VisuAlgo contains many advanced algorithms that are discussed in Dr Steven Halim’s book (‘Competitive Programming’, co-authored with his brother Dr Felix Halim) and beyond. Today, some of these advanced algorithms visualization/animation can only be found in VisuAlgo.

Though specifically designed for National University of Singapore (NUS) students taking various data structure and algorithm classes (e.g. CS1010, CS1020, CS2010, CS2020, CS3230, and CS3230), as advocators of online learning, we hope that curious minds around the world will find these visualisations useful too.

VisuAlgo is not designed to work well on small touch screens (e.g. smartphones) from the outset due to the need to cater for many complex algorithm visualizations that require lots of pixels and click-and-drag gestures for interaction. The minimum screen resolution for a respectable user experience is 1024×768 and only the landing page is relatively mobile-friendly.

VisuAlgo is an ongoing project and more complex visualisations are still being developed.

The most exciting development is the automated question generator and verifier (the online quiz system) that allows students to test their knowledge of basic data structures and algorithms. The questions are randomly generated via some rules and students’ answers are instantly and automatically graded upon submission to our grading server. This online quiz system, when it is adopted by more CS instructors worldwide, should technically eliminate manual basic data structure and algorithm questions from typical Computer Science examinations in many Universities. By setting a small (but non-zero) weightage on passing the online quiz, a CS instructor can (significantly) increase his/her students mastery on these basic questions as the students have virtually infinite number of training questions that can be verified instantly before they take the online quiz. The training mode currently contains questions for 12 visualization modules. We will soon add the remaining 8 visualization modules so that every visualization module in VisuAlgo have online quiz component.

Another active branch of development is the internationalization sub-project of VisuAlgo. We want to prepare a database of CS terminologies for all English text that ever appear in VisuAlgo system. This is a big task and requires crowdsourcing. Once the system is ready, we will invite VisuAlgo visitors to contribute, especially if you are not a native English speaker. Currently, we have also written public notes about VisuAlgo in various languages:
zh, id, kr, vn, th.

Команда

Руководитель Проекта и Советник (июль 2011 по настоящее время)
Dr Steven Halim, Senior Lecturer, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Software Engineer, Google (Mountain View)

Научные Проекты Студентов Программы Бакалаврата 1 (Jul 2011-Apr 2012)
Koh Zi Chun, Victor Loh Bo Huai

Final Year Project/UROP students 1 (Jul 2012-Dec 2013)
Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy

Final Year Project/UROP students 2 (Jun 2013-Apr 2014)
Rose Marie Tan Zhao Yun, Ivan Reinaldo

Научные Проекты Студентов Программы Бакалаврата 2 (May 2014-Jul 2014)
Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

Final Year Project/UROP students 3 (Jun 2014-Apr 2015)
Erin Teo Yi Ling, Wang Zi

Final Year Project/UROP students 4 (Jun 2016-Dec 2017)
Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir

List of translators who have contributed ≥100 translations can be found at statistics page.

Acknowledgements
Этот проект стал возможным благодаря щедрому гранту по Улучшению Процесса Обучения, выданного центром Национального университета Сингапура по Развитию Процесса Обучения (CDTL).

Условия использования

VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the only payment that we ask of you is for you to tell the existence of VisuAlgo to other Computer Science students/instructors that you know =) via Facebook, Twitter, course webpage, blog review, email, etc.

If you are a data structure and algorithm student/instructor, you are allowed to use this website directly for your classes. If you take screen shots (videos) from this website, you can use the screen shots (videos) elsewhere as long as you cite the URL of this website (http://visualgo.net) and/or list of publications below as reference. However, you are NOT allowed to download VisuAlgo (client-side) files and host it on your own website as it is plagiarism. As of now, we do NOT allow other people to fork this project and create variants of VisuAlgo. Using the offline copy of (client-side) VisuAlgo for your personal usage is fine.

Note that VisuAlgo’s online quiz component is by nature has heavy server-side component and there is no easy way to save the server-side scripts and databases locally. Currently, the general public can only use the ‘training mode’ to access these online quiz system. Currently the ‘test mode’ is a more controlled environment for using these randomly generated questions and automatic verification for a real examination in NUS. Other interested CS instructor should contact Steven if you want to try such ‘test mode’.

List of Publications

This work has been presented briefly at the CLI Workshop at the ACM ICPC World Finals 2012 (Poland, Warsaw) and at the IOI Conference at IOI 2012 (Sirmione-Montichiari, Italy). You can click this link to read our 2012 paper about this system (it was not yet called VisuAlgo back in 2012).

This work is done mostly by my past students. The most recent final reports are here: Erin, Wang Zi, Rose, Ivan.

Bug Reports or Request for New Features

VisuAlgo is not a finished project. Dr Steven Halim is still actively improving VisuAlgo. If you are using VisuAlgo and spot a bug in any of our visualization page/online quiz tool or if you want to request for new features, please contact Dr Steven Halim. His contact is the concatenation of his name and add gmail dot com.

7) Двоичное дерево поиска — CoderLessons.com

Что такое дерево бинарного поиска?

Бинарное дерево поиска — это расширенный алгоритм, используемый для анализа узла, его левой и правой ветвей, которые смоделированы в древовидной структуре и возвращают значение. BST разработан на основе архитектуры основного алгоритма двоичного поиска; следовательно, он обеспечивает более быстрый поиск, вставку и удаление узлов. Это делает программу действительно быстрой и точной.

В этом уроке по структуре данных вы узнаете:

Атрибуты бинарного дерева поиска

BST состоит из нескольких узлов и состоит из следующих атрибутов:

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

Существует главный узел или родительский уровень 11. Под ним находятся левый и правый узлы / ветви со своими собственными значениями ключей.
Правое поддерево имеет значения ключа больше, чем родительский узел
Левое поддерево имеет значения, чем родительский узел

Зачем нам нужно дерево двоичного поиска?

Двумя основными факторами, которые делают бинарное дерево поиска оптимальным решением любых реальных проблем, являются Скорость и Точность.
Из-за того, что бинарный поиск имеет ветвистый формат с отношениями родитель-потомок, алгоритм знает, в каком месте дерева нужно искать элементы. Это уменьшает количество сравнений ключ-значение, которые должна выполнить программа, чтобы найти нужный элемент.
Кроме того, в случае, если элемент для поиска больше или меньше, чем родительский узел, узел знает, какую сторону дерева искать. Причина в том, что левое поддерево всегда меньше родительского узла, а правое поддерево имеет значения, всегда равные или превышающие родительский узел.
BST обычно используется для реализации сложного поиска, надежной игровой логики, операций автозавершения и графики.
Алгоритм эффективно поддерживает такие операции, как поиск, вставка и удаление.

Типы бинарных деревьев

Три вида бинарных деревьев:

Полное двоичное дерево: все уровни в деревьях полны возможных исключений последнего уровня. Точно так же все узлы заполнены, направляя крайний левый.
Полное двоичное дерево: все узлы имеют 2 дочерних узла, кроме листа.
Сбалансированное или совершенное двоичное дерево: в дереве все узлы имеют двух дочерних элементов. Кроме того, уровень каждого подузла одинаковый.

Как работает дерево бинарного поиска?

Дерево всегда имеет корневой узел и дополнительные дочерние узлы, слева или справа. Алгоритм выполняет все операции, сравнивая значения с корневым и его дальнейшими дочерними узлами в левом или правом поддереве соответственно.

Зависит от того, какой элемент будет вставлен, найден или удален, после сравнения алгоритм может легко удалить левое или правое поддерево корневого узла.

BST в первую очередь предлагает следующие три типа операций для вашего использования:

Поиск: поиск элемента из двоичного дерева
Вставить: добавляет элемент в двоичное дерево
Удалить: удалить элемент из двоичного дерева

Каждая операция имеет свою структуру и метод выполнения / анализа, но наиболее сложной из них является операция удаления.

Операция поиска

Всегда инициируйте анализ дерева в корневом узле, а затем двигайтесь дальше к правому или левому поддереву корневого узла, в зависимости от того, какой элемент должен быть меньше или больше корневого.

Элемент для поиска — 10
Сравните элемент с корневым узлом 12, 10 <12, следовательно, вы переместитесь в левое поддерево. Не нужно анализировать правильное поддерево
Теперь сравните 10 с узлом 7, 10> 7, поэтому перейдите к правому поддереву
Затем сравните 10 со следующим узлом, который является 9, 10> 9, посмотрите в дочернем поддереве справа
10 соответствует значению в узле, 10 = 10, возвращает значение пользователю.

Операция вставки

Это очень прямолинейная операция. Сначала вставляется корневой узел, затем сравнивается следующее значение с корневым узлом. Если значение больше корневого, оно добавляется к правому поддереву, а если оно меньше корневого, оно добавляется к левому поддереву.

Существует список из 6 элементов, которые необходимо вставить в BST по порядку слева направо
Вставьте 12 в качестве корневого узла и сравните следующие значения 7 и 9 для вставки соответственно в правое и левое поддерево.
Сравните остальные значения 19, 5 и 10 с корневым узлом 12 и разместите их соответствующим образом. 19> 12 поместите его как правого ребенка 12, 5 <12 и 5 <7, следовательно, поместите его как левого ребенка 7 лет.
1. Теперь сравните 10, 10 — это <12, а 10 -> 7 и 10 -> 9, поместите 10 как правильное поддерево 9.

Операции удаления

Удалить является наиболее продвинутым и сложным среди всех других операций. В BST обрабатывается несколько дел.

Случай 1 — Узел с нулевыми дочерними элементами: это самая простая ситуация, вам просто нужно удалить узел, у которого больше нет дочерних элементов справа или слева.
Случай 2 — Узел с одним дочерним узлом: после удаления узла просто подключите его дочерний узел с родительским узлом удаленного значения.
Пример 3 Узел с двумя детьми: это самая сложная ситуация, и она работает по следующим двум правилам
- 3a — В Предшественнике заказа: вам нужно удалить узел с двумя дочерними элементами и заменить его наибольшим значением в левом поддереве удаленного узла.
- 3b — В порядке преемника: необходимо удалить узел с двумя дочерними элементами и заменить его наибольшим значением в правом поддереве удаленного узла

Это первый случай удаления, при котором вы удаляете узел, у которого нет дочерних элементов. Как видно из диаграммы, 19, 10 и 5 не имеют детей. Но мы удалим 19.
Удалите значение 19 и удалите ссылку из узла.
Посмотреть новую структуру BST без 19

Это второй случай удаления, при котором вы удаляете узел, у которого есть 1 дочерний элемент, как вы можете видеть на диаграмме, что у 9 есть один дочерний элемент.
Удалите узел 9, замените его дочерним 10 и добавьте ссылку с 7 на 10.
Посмотреть новую структуру BST без 9

Здесь вы будете удалять узел 12, который имеет двух детей
Удаление узла будет происходить на основе правила предшественника по порядку, что означает, что его заменит самый большой элемент в левом поддереве из 12.
Удалите узел 12 и замените его на 10, так как это наибольшее значение в левом поддереве.
Просмотр новой структуры BST после удаления 12

1 Удалите узел 12 с двумя дочерними элементами.
2 Удаление узла будет происходить на основе правила преемника по порядку, что означает, что его заменит самый большой элемент в правом поддереве из 12
3 Удалите узел 12 и замените его на 19, так как это наибольшее значение в правом поддереве.
4 Просмотр новой структуры BST после удаления 12

Важные условия

Вставить — вставляет элемент в дерево / создает дерево.
Поиск — поиск элемента в дереве.
Preorder Traversal — обход дерева по предзаказу.
Inorder Traversal — обход дерева по порядку.
Postorder Traversal — обход дерева по порядку заказа.

Резюме

BST — это алгоритм продвинутого уровня, который выполняет различные операции на основе сравнения значений узлов с корневым узлом.
Любая из точек в иерархии родитель-потомок представляет узел. По крайней мере один родительский или корневой узел остается постоянно.
Есть левое поддерево и правое поддерево. Левое поддерево содержит значения, которые меньше корневого узла. Однако правое поддерево содержит значение, которое больше корневого узла.
Каждый узел может иметь ноль, одного или двух дочерних элементов.
Двоичное дерево поиска облегчает основные операции, такие как поиск, вставка и удаление.
У удаления, являющегося наиболее сложным, есть несколько случаев, например, узел без дочернего элемента, узел с одним дочерним элементом и узел с двумя дочерними элементами.
Алгоритм используется в реальных решениях, таких как игры, автозаполнение данных и графика.

Введение в структуру данных двоичного дерева

Мы начинаем новую область компьютерных наук. Если у вас есть несколько лет опыта в области компьютерных наук или исследований, и вы заинтересованы в том, чтобы поделиться этим опытом с сообществом (и, конечно же, получать деньги за свою работу), загляните на страницу «Напишите для нас».
Ура, Евгений

1. Введение

В этой статье мы собираемся изучить структуру данных двоичного дерева и его свойства. Далее мы изучим шесть типов двоичных деревьев с иллюстрациями.

Наконец, мы рассмотрим различные применения двоичного дерева.

2. Определение

Двоичное дерево — это иерархическая структура данных, в которой каждый узел имеет не более двух дочерних элементов . Дочерние узлы называются левым и правым.

Для начала давайте опишем представление связного списка двоичного дерева, в котором каждый узел имеет три поля:

Указатель для хранения адреса левого дочернего элемента
Элемент данных
Указатель для хранения адреса правого ребенка

Давайте посмотрим на пример двоичного дерева:

3.Недвижимость

Давайте теперь сосредоточимся на некоторых основных свойствах двоичного дерева:

Двоичное дерево может иметь максимум узлов на уровне, если уровень корня равен нулю.
Когда каждый узел двоичного дерева имеет одного или двух дочерних узлов, количество конечных узлов (узлов без дочерних) на единицу больше, чем количество узлов, у которых есть два дочерних элемента.
В двоичном дереве существует максимум узлов, если его высота равна, а высота конечного узла равна единице.
Если в двоичном дереве существуют конечные узлы, то оно имеет как минимум уровни.
Бинарное дерево узлов имеет минимальное количество уровней или минимальную высоту.
Минимальная и максимальная высота двоичного дерева, имеющего узлы, равны и, соответственно.
Бинарное дерево узлов имеет пустые ссылки.

4. Типы двоичных деревьев

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

4.1. Полное двоичное дерево

Двоичное дерево называется полным двоичным деревом, если каждый внутренний узел имеет ноль или два дочерних элемента. :

4.2. Совершенное двоичное дерево

Совершенное двоичное дерево — это особый тип двоичного дерева, в котором все конечные узлы находятся на одном уровне, а каждый внутренний узел имеет двух дочерних узлов :

4.3. Полное двоичное дерево

Двоичное дерево называется полным двоичным деревом, когда все его уровни полностью заполнены. Единственным исключением, возможно, является самый нижний уровень, на котором узлы должны наклоняться как можно левее:

4.4. Вырожденное или патологическое дерево

Вырожденное или патологическое дерево — это тип двоичного дерева, в котором каждый внутренний узел имеет одного дочернего элемента , либо левый, либо правый дочерний элемент:

4.5. Перекошенное двоичное дерево

Двоичное дерево называется перекошенным двоичным деревом, если все его внутренние узлы имеют ровно одного дочернего элемента, а либо левые, либо правые дочерние элементы доминируют в дереве . В частности, существует два типа скошенных двоичных деревьев: скошенное влево двоичное дерево и скошенное вправо двоичное дерево :

4.6. Сбалансированное двоичное дерево

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

5.Приложения

Существует множество других структур данных, которые являются производными от идеи двоичного дерева, например, двоичное дерево поиска, синтаксическое дерево, куча, хеш-дерево, красно-черное дерево, двоичное дерево, дерево AVL, дерево GGM, T-дерево, и Треап.

Другие реальные приложения двоичного дерева включают разделение двоичного пространства, сортировку кучи, кодирование Хаффмана, управление виртуальной памятью и индексацию.

6. Заключение

В этой статье мы изучили структуру данных двоичного дерева вместе с его основными свойствами.

Затем мы обсудили шесть типов двоичных деревьев с наглядными примерами. Наконец, мы перечислили различные применения двоичного дерева.

4.2 Бинарные деревья

следующий: 4.3
Применение двоичных деревьев: построение кода Хаффмана Up: 4.
Двоичные деревья Предыдущая: 4.1.4
Структуры данных для представления в виде дерева

Определение: Двоичное дерево либо пусто, , либо состоит из
узел, называемый
корень вместе с двумя бинарными деревьями, называемыми
осталось
поддерево и правое поддерево .

**Рисунок 4.6:** Примеры полных, неполных двоичных деревьев

Обход двоичного дерева:

1.: Предзаказ
2.: Рассылка
3.: Для заказа

На рисунке 4.7 показано несколько двоичных файлов.
деревья и последовательности обхода в предварительном, неупорядоченном и последующем порядке.
Мы можем построить двоичное дерево однозначно из предварительного порядка и порядка или
postorder и inorder , но не preorder и postorder .

**Рисунок 4.7:** Обход двоичного дерева

Структуры данных для двоичных деревьев:

1.: Массивы , особенно подходящие для полных и полных двоичных деревьев
2.: На основе указателя

Реализация на основе указателя:

typedef struct node-tag {

информация о типе элемента;

структура
узел-тег * слева;

структура
узел-тег * справа;

} узел-тип;

тип узла * корень
; / * указатель на корень * /

узел-тип * п; / *
временный указатель * /

аннулировано предзаказ (тип узла *
корень)

{

if (root) {

визит (корень);

предзаказ (root
оставили) ;

предзаказ (root
верно) ;

}

void inorder (тип узла *
корень)

{

if (root) {

inorder (корень
оставили) ;

визит (корень);

inorder (корень
верно) ;

}

}

void postorder (тип узла *
корень)

{

если (корень) {

почтовый заказ (корень
оставили) ;

почтовый заказ (корень
верно) ;

визит (корень);

}

Далее: 4.3
Применение двоичных деревьев: построение кода Хаффмана Up: 4.
Двоичные деревья Предыдущая: 4.1.4
Структуры данных для представления в виде дерева

eEL, CSA_Dept, IISc, Бангалор

Двоичное дерево и его типы | Учебник по структуре данных

Двоичное дерево — это иерархическая структура данных, в которой каждый узел имеет не более двух дочерних элементов, обычно называемых левым и правым дочерними элементами.

Каждый узел содержит три компонента:

Указатель на левое поддерево
Указатель на правое поддерево
Элемент данных

Самый верхний узел в дереве называется корнем.Пустое дерево представлено указателем NULL .

Показано представление двоичного дерева:

Двоичное дерево: общие термины

Корень: Самый верхний узел в дереве.
Родитель: Каждый узел (за исключением корня) в дереве соединен направленным ребром ровно от одного другого узла. Этот узел называется родительским.
Дочерний: Узел, напрямую подключенный к другому узлу при удалении от корня.
Листовой / Внешний узел: Узел без дочерних узлов.
Внутренний узел: Узел по крайней мере с одним дочерним элементом.
Глубина узла: Количество ребер от корня до узла.
Высота узла: Количество ребер от узла до самого глубокого листа. Высота дерева — это высота корня.

В приведенном выше двоичном дереве мы видим, что корневой узел — это A . Дерево имеет 10 узлов с 5 внутренними узлами, т.е.e, A, B, C, E, G и 5 внешних узлов, то есть D, F, H, I, J . Высота дерева — 3. B является родительским элементом для D и E , а D и E являются дочерними элементами B .

Преимущества деревьев

Деревья настолько полезны и часто используются, потому что у них есть очень серьезные преимущества:

Деревья отражают структурные взаимосвязи в данных.
Деревья используются для представления иерархий.
Деревья обеспечивают эффективную вставку и поиск.
Деревья — это очень гибкие данные, позволяющие перемещать поддеревья с минимальными усилиями.

Типы двоичных деревьев (на основе структуры)

Бинарное дерево с корнем: У него есть корневой узел, и каждый узел имеет не более двух дочерних элементов.
Полное двоичное дерево: Это дерево, в котором каждый узел в дереве имеет либо 0, либо 2 дочерних элемента.
- Количество узлов, n , в полном двоичном дереве как минимум n = 2h — 1, и самое большее n = 2 ^{h + 1}-1 , где h — высота дерева .
- Количество конечных узлов l , в полном двоичном дереве это число, L внутренних узлов + 1, т. Е. l = L + 1 .
Совершенное двоичное дерево: Это двоичное дерево, в котором все внутренние узлы имеют двух дочерних элементов, а все листья имеют одинаковую глубину или одинаковый уровень.
- Совершенное бинарное дерево с l листьями имеет n = 2l-1 узла.
- В идеальном полном двоичном дереве l = 2h и n = 2h + 1 — 1 , где n — количество узлов, h — высота дерева и l — количество листовых узлов
Полное двоичное дерево: Это двоичное дерево, в котором каждый уровень, кроме, возможно, последнего, полностью заполнен, а все узлы расположены как можно дальше слева.
- Количество внутренних узлов в полном двоичном дереве из n узлов составляет этаж (n / 2) .
Сбалансированное двоичное дерево: Двоичное дерево сбалансировано по высоте, если оно удовлетворяет следующим ограничениям:
1. Высота левого и правого поддеревьев различается не более чем на единицу, И
2. Левое поддерево сбалансировано, И
3. Правое поддерево сбалансировано
Пустое дерево сбалансировано по высоте.
- Высота сбалансированного двоичного дерева равна O ( Log n ), где n — количество узлов.
Дерево дегенерации: Это дерево, в котором каждый родительский узел имеет только один дочерний узел. Он ведет себя как связанный список.

Объяснение деревьев двоичного поиска · YourBasic

yourbasic.org

Определения двоичного дерева

Двоичное дерево — это структура данных, которую проще всего описать с помощью рекурсии.

Бинарное дерево
либо пусто,
или состоит из узла
(также известный как корень дерева) и два поддерева,
левое и правое поддеревья, которые также являются бинарными деревьями.

Узел с двумя пустыми поддеревьями называется листом .

Если p — узел, а q — корень
p Поддерево , мы говорим, что
p — родитель из q
и что q является дочерним элементом из p .
Два узла с одними и теми же родителями называются дочерними узлами .

Набор предков , если узел n
определяется рекурсивно этими двумя правилами:

n является предком n .
Если q является потомком p и
q является предком n , тогда
p также является предком n .

Набор предков узла n
образуют путь от n
к корню дерева.

Глубина узла — это количество элементов на пути от
узел к корню.

Глубина дерева определяется как самая большая глубина из всех
узел в дереве.Пустое дерево имеет глубину 0.

Дерево двоичного поиска

Дерево двоичного поиска — это двоичное дерево, в котором каждый узел содержит
значение из упорядоченного набора.

Для каждый узел n в двоичном дереве поиска
имеют место следующие инварианты.

Каждый узел в левом поддереве из n содержит
значение, которое на меньше на , чем значение в узле n .
Каждый узел в правом поддереве из n содержит
значение, которое на больше, чем на значение в узле n .

Пример

Это двоичное дерево имеет 9 узлов и глубину 4.

Корень дерева содержит значение 8.
Значения листа: 1, 4, 7 и 13.

Каждый узел в левом поддереве имеет значение меньше 8,
, в то время как каждый узел в правом поддереве имеет значение больше 8.

По сути, это двоичное дерево поиска, так как
соответствующий инвариант сохраняется для каждого узла в дереве.

Сбалансированные деревья с временной сложностью O (log n)

Мы говорим, что дерево хорошо сбалансировано , если каждый узел в дереве имеет
два поддерева с примерно одинаковым количеством узлов.Можно показать, что хорошо сбалансированное дерево с n узлами
имеет глубину O (бревно n ).

Если нам удастся сохранить сбалансированное двоичное дерево поиска,
мы получаем упорядоченную структуру данных с
O (log n ) наихудшая временная сложность для всех основных операций:
поиск, добавление и удаление.

Есть несколько более или менее сложных стратегий
чтобы дерево двоичного поиска было хорошо сбалансированным.

деревья AVL были первыми,
Красно-черные деревья используются Java’s TreeSet ,
Treaps , рандомизированные бинарные деревья поиска, просты и элегантны.

См. Статью Treaps: randomized search tree
для полного описания treaps.

В этом тексте мы представляем псевдокод только для некоторых основных операций.
на несбалансированных деревьях двоичного поиска.

Предупреждение: Несбалансированное дерево может быть очень неэффективным.
В самом крайнем случае, например, когда все левые поддеревья пусты,
дерево превращается в односвязный список.

Древовидные алгоритмы

Перемещение по порядку

Обход бинарного дерева поиска по порядку посещает узлы в отсортированном порядке.

// Обходим все узлы двоичного дерева поиска в отсортированном порядке.
  Алгоритм  inorder (корень)
      если корень  пуст
        // ничего не делать
      еще 
        inorder (root.left)
        // что-то делаем с root
        inorder (root.right)

Поиск

Реализовать операцию поиска довольно просто.
в двоичном дереве поиска с итерацией, но для
Будьте проще, вот рекурсивная версия.

// Возвращает истину, если значение найдено в дереве. Алгоритм  find (значение, корень)
      если корень  пуст
        вернуть ложь
     , если значение  = root.value
        вернуть истину
     , если значение   еще 
        вернуть find (значение, root.right)

Вставка

Для реализации алгоритма, изменяющего структуру дерева,
удобно определить функцию, которая берет корень старого дерева
в качестве входных данных и возвращает корень нового обновленного дерева.

// Добавляет новый узел и возвращает корень обновленного дерева.
  Алгоритм  insert (узел, корень)
      если корень  пуст
        возвратный узел
     , если  node.value = root.value
        // ничего не делаем, элемент уже в дереве
      иначе   если  node.value  еще 
        root.right ← insert (узел, root.right)
    вернуть корень

Поделиться:

Структура данных двоичного дерева | Торт для интервью

Двоичное дерево — это дерево , в котором каждый узел имеет двух или меньше дочерних элементов.Детей обычно называют левыми и правыми.

открытый класс BinaryTreeNode {

общедоступное значение int;
public BinaryTreeNode left;
публичное право BinaryTreeNode;

public BinaryTreeNode (int value) {
this.value = значение;
}
}

Это позволяет нам построить такую структуру:

Этот конкретный пример особенный, потому что каждый уровень дерева полностью заполнен. Нет никаких «пробелов». Мы называем это дерево « совершенное ».»

У бинарных деревьев есть несколько интересных свойств, когда они идеальны:

Свойство 1: количество общих узлов на каждом «уровне» удваивается по мере продвижения вниз по дереву.

Свойство 2: количество узлов на последнем уровне равно сумме количества узлов на всех остальных уровнях (плюс 1).

Другими словами, примерно , половина наших узлов находятся на последнем уровне.

Назовем количество узлов n, а высоту дерева h.{час})}
\ log_ {2} {(n + 1)} = h

Это соотношение между высотой и общим количеством узлов в идеальном двоичном дереве.

20+ проблем кодирования двоичного дерева из интервью по программированию | автор: javinpaul | Javarevisited

Привет, ребята, я делился множеством ресурсов о собеседованиях по программированию, таких как книги, курсы и некоторые вопросы для собеседований по дизайну программного обеспечения и структурам данных, таким как массив, строка и связанный список.

До сих пор мы рассматривали только линейные структуры данных , такие как массив и связанный список, но вся информация в реальном мире не может быть представлена линейно, и здесь помогает древовидная структура данных.

Древовидная структура данных — это иерархическая структура данных, которая позволяет хранить иерархические данные, такие как семейное древо или офисная иерархия. В зависимости от того, как вы храните данные, существуют разные типы деревьев, такие как двоичное дерево, где каждый узел имеет не более двух дочерних узлов.

Наряду со своим близким родственником двоичного дерева поиска оно также является одним из наиболее распространенных. популярные древовидные структуры данных. Следовательно, вы найдете много вопросов, основанных на них, например, как их пройти, подсчитать узлы, найти глубину и проверить, сбалансированы ли они или нет.

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

Если вы не знакомы с этими концепциями, я настоятельно рекомендую вам сначала пройти комплексный курс по структуре данных и алгоритмам, например Структуры данных и алгоритмы: глубокое погружение с использованием Java , в котором подробно объясняется важная структура данных.Это также очень доступно, так как вы можете купить этот курс всего за 9,9 доллара на сумасшедших распродажах Udemy, которые случаются время от времени.

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

Как реализовано двоичное дерево поиска? ( решение )
Как вы выполняете предварительный обход в заданном двоичном дереве? ( решение )
Как пройти по заданному двоичному дереву в предварительном порядке без рекурсии? ( решение )
Как выполнить обход в заданном двоичном дереве? ( решение )
Как распечатать все узлы данного двоичного дерева, используя обход по порядку без рекурсии? ( решение )
Как реализовать алгоритм обхода после порядкового номера? ( решение )
Как пройти по двоичному дереву без рекурсии при обходе после порядка? ( решение )
Как печатаются все листья двоичного дерева поиска? ( решение )
Как подсчитать количество конечных узлов в данном двоичном дереве? ( решение )
Как выполнить двоичный поиск в заданном массиве? ( решение )
Как преобразовать заданное двоичное дерево в список с двойной связью в Java? (решение)
Написать программу для определения глубины заданного двоичного дерева на Java? (решение)
В чем разница между двоичным и двоичным деревьями поиска? (ответ)
Что такое самоуравновешенное дерево? (ответ)
Что такое дерево AVL? (ответ)
Вы дали BST, где два узла меняются местами? Как восстановить исходный BST? (решение)
Как преобразовать двоичное дерево в двоичное дерево поиска в Java? (решение)
Найти самое большое поддерево BST данного двоичного дерева в Java? (решение)
Написать программу на Java для соединения узлов на том же уровне, что и двоичное дерево? (решение)
Что такое структура данных Trie? (ответ)
В чем разница между двоичным деревом и деревом Trie? (ответ)

Это одни из самых популярных вопросов на основе двоичного дерева, которые задают на собеседовании при приеме на работу программиста.Вы можете решить их, чтобы освоиться с проблемами на основе дерева.

Если вы чувствуете, что ваше понимание кодирования двоичного дерева недостаточно, и вы не можете решить эти вопросы самостоятельно, я предлагаю вам вернуться и выбрать хорошую структуру данных и курсы алгоритмов, такие как Easy to Advanced Data Structures by William Фисет, бывший инженер Google и бывший финалист конкурса ACM-ICPC world , чтобы освежить свои знания о двоичном дереве и двоичном дереве поиска.

Если вам нужны дополнительные рекомендации, вот мой список полезных книг и курсов по алгоритмам структуры данных для начала.

Теперь вы на шаг ближе к собеседованию по кодированию

Это одни из наиболее распространенных вопросов о собеседованиях по кодированию в форме структуры данных бинарного дерева, которые помогут вам добиться хороших результатов на собеседовании.

Я также поделился множеством вопросов о структуре данных в своем блоге, поэтому, если вам действительно интересно, вы всегда можете пойти туда и найти их.

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

Если вы ищете работу в области программирования или разработки программного обеспечения в 2021 году, вы можете начать подготовку с этого списка вопросов по кодированию.

Этот список содержит хорошие темы для подготовки, а также помогает оценить вашу подготовку, чтобы определить свои сильные и слабые стороны.

Хорошее знание структуры данных и алгоритмов важно для успеха при написании кода собеседований, и именно на этом вам следует сосредоточить большую часть своего внимания.

Дальнейшее обучение

Собеседование по программированию: шаблоны для вопросов по кодированию
Структуры данных и алгоритмы: глубокое погружение с использованием Java
Анализ структуры данных и алгоритмов — Собеседование
Алгоритмы и структура данных Часть 1 и 2
Структуры данных в Java: Интервью Refresher
Grokking Шаблоны динамического программирования для программирования Интервью

Заключительные примечания

Спасибо, вы дочитали статью до конца … Удачи вам в вашем собеседовании по программированию! Конечно, это будет непросто, но, следуя этой дорожной карте и руководству, вы на один шаг ближе к тому, чтобы стать разработчиком программного обеспечения.

Если вам понравилась эта статья, поделитесь ею со своими друзьями и коллегами и не забудьте подписаться на javinpaul в Twitter!

П.С. — Если вам нужны БЕСПЛАТНЫЕ ресурсы, вы можете проверить этот список бесплатных курсов по структуре данных и алгоритмам, чтобы начать подготовку.

Двоичная древовидная структура данных | Журнал разработки Java

В этом посте мы рассмотрим структуру данных бинарного дерева и . Мы увидим разные деревья и их характеристики.

Введение

Структура данных двоичного дерева — это иерархическая структура данных, в которой каждый элемент имеет максимум 2 дочерних элемента. Мы называем этих детей левым и правым ребенком. В следующем примере левое дерево является двоичным деревом, а правое — нет.

В правой древовидной структуре у нас есть более 2 дочерних узлов для родительского узла 2. Давайте посмотрим на некоторые точки для двоичного дерева.

Каждый узел содержит указатель на левое и правое поддеревья.
Каждый узел содержит элемент данных.

Если в дереве всего 1 узел, это тоже двоичное дерево.

Узлы в примерах изображений только помечены и не представляют номер / данные для дерева.

2. Терминология двоичного дерева

Прежде чем мы подробно рассмотрим структуру данных двоичного дерева , давайте обновим некоторую общую терминологию.

Корневой узел: — Самый верхний узел является корневым узлом (узел 1 является корневым узлом).
Мы определяем дерево по родительским и дочерним узлам.
Родительский узел: Каждый узел (за исключением корня) в дереве соединен направленным ребром ровно от одного другого узла. Этот узел называется родительским.
Конечные узлы: узлы, не имеющие дочерних узлов.
Высота: высота дерева — это максимальное количество ребер от узла до самого дальнего листового узла.
Глубина: количество ребер от корневого узла до узла.
Размер: Размер дерева — это общее количество содержащихся в нем узлов.

Если вы ищете Реализация кода дерева двоичного поиска. Прочтите «Реализация двоичного дерева поиска в Java».

3. Типы двоичных деревьев

Прежде чем мы перейдем к другим деталям, давайте обсудим различные типы дерева. Я расскажу о самых популярных древовидных структурах.

3.1 Полное двоичное дерево

Полное двоичное дерево — это дерево, в котором каждый узел имеет 0 или 2 дочерних элемента.Ни у одного узла не будет только одного дочернего элемента.

3.2 Полное двоичное дерево

Дерево, в котором каждый уровень полностью заполнен (имеет 2 детей), за исключением, возможно, последнего уровня. Для полного двоичного дерева мы заполняем последний уровень слева направо.

3.3 Совершенное двоичное дерево

A совершенное бинарное дерево одновременно полное и полное. Все листья имеют одинаковую глубину или одинаковый уровень.

Идеальное дерево очень редко.

4. Обход двоичного дерева

Обход дерева — это процесс посещения всех узлов. На высоком уровне мы можем сгруппировать обход дерева в следующие 2 группы.

Обход в глубину.
Обход в ширину.

Для обхода в ширину мы посещаем узлы дерева по уровням сверху вниз и слева направо. Для обхода в глубину; у нас есть следующие основные параметры обхода (также посмотрите на следующее дерево для примера вывода)

4.1 Порядок обхода

Для обхода по порядку мы посещаем левую ветвь, затем текущий узел и, наконец, правую ветвь нашего дерева. Если мы выполним обход по порядку в двоичном дереве поиска , мы получим данные в порядке возрастания. Вот снимок экрана, на котором показан обход по порядку.

Число показывает последовательность обхода в дереве.

Выход: 9, 5, 1, 7, 2, 12, 8, 4, 3, 11

4.2 Обход предварительного заказа

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

Выход: 8, 5, 9, 7, 1, 12, 2, 4, 11, 3

4.3 Обход пост-заказа

При обходе после заказа мы посещаем левое дерево, затем правое дерево и, наконец, родительское дерево. Давайте посмотрим, как выглядит последовательность обхода:

Выход: 9, 1, 2, 12, 7, 5, 3, 11, 4, 8

5. Деревья двоичного поиска

A двоичное дерево поиска — это специализированное дерево, которое выполняет следующие свойства:

Каждый узел содержит определенные данные.
Данные в левом поддереве всегда меньше, чем у родительского узла.
Данные в правом поддереве всегда больше, чем у родительского узла.

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

6. Сбалансированное и несбалансированное двоичное дерево

Два двоичных дерева поиска могут хранить одни и те же значения по-разному:

Сбалансированное дерево — это дерево, в котором

Высота левого и правого поддеревьев различается не более чем на единицу.
Левое поддерево сбалансировано.
Правое поддерево сбалансировано

7. Время Complexirty BST

	Среднее значение	Худшее
Пространство	О (н)	О (н)
Вставка	O (lg (n))	О (н)
Поиск	О (lg (n))	О (н)
Удалить	О (lg (n))	О (н)

Апрель 2024
Пн	Вт	Ср	Чт	Пт	Сб	Вс
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

Двоичное дерево: Бинарные деревья поиска и рекурсия – это просто / Хабр

Разница между «полным двоичным деревом»,»строгим двоичным деревом», «полным двоичным деревом»?

Двоичное дерево поиска, определение свойства, операции Струк…

Содержание

Основные операции в двоичном дереве поиска

Удаление (второй пример)

Балансировка дерева

См. также

Бинарное (двоичное) дерево поиска, обходы и применение

Бинарное дерево на Go для новичка

Введение

Что такое дерево?

Зачем нужны бинарные деревья?

Терминология

Дерево бинарного поиска на Go

Вставка узла в дерево

Извлечение минимума

Извлечение максимума

Обход бинарного дерева

Заключение

«Меня только что попросили сбалансировать двоичное дерево поиска в аэропорту» Статьи редакции

VisuAlgo — Двоичное Поисковое Дерево, АВЛ-дерево

О нас

Команда

Условия использования

7) Двоичное дерево поиска — CoderLessons.com

Что такое дерево бинарного поиска?

Атрибуты бинарного дерева поиска

Зачем нам нужно дерево двоичного поиска?

Типы бинарных деревьев

Как работает дерево бинарного поиска?

Операция поиска

Операция вставки

Операции удаления

Важные условия

Резюме

Введение в структуру данных двоичного дерева

1. Введение

2. Определение

3.Недвижимость

4. Типы двоичных деревьев

4.1. Полное двоичное дерево

4.2. Совершенное двоичное дерево

4.3. Полное двоичное дерево

4.4. Вырожденное или патологическое дерево

4.5. Перекошенное двоичное дерево

4.6. Сбалансированное двоичное дерево

5.Приложения

6. Заключение

4.2 Бинарные деревья

Двоичное дерево и его типы | Учебник по структуре данных

Двоичное дерево: общие термины

Преимущества деревьев

Типы двоичных деревьев (на основе структуры)

Объяснение деревьев двоичного поиска · YourBasic

Определения двоичного дерева

Дерево двоичного поиска

Пример

Сбалансированные деревья с временной сложностью O (log n)

Древовидные алгоритмы

Перемещение по порядку

Поиск

Вставка

Структура данных двоичного дерева | Торт для интервью

20+ проблем кодирования двоичного дерева из интервью по программированию | автор: javinpaul | Javarevisited

Теперь вы на шаг ближе к собеседованию по кодированию

Заключительные примечания

П.С. — Если вам нужны БЕСПЛАТНЫЕ ресурсы, вы можете проверить этот список бесплатных курсов по структуре данных и алгоритмам, чтобы начать подготовку.

Двоичная древовидная структура данных | Журнал разработки Java

Введение

2. Терминология двоичного дерева

3. Типы двоичных деревьев

3.1 Полное двоичное дерево

3.2 Полное двоичное дерево

3.3 Совершенное двоичное дерево

4. Обход двоичного дерева

4.1 Порядок обхода

4.2 Обход предварительного заказа

4.3 Обход пост-заказа

5. Деревья двоичного поиска

8.
No related posts.