Дерево двоичного поиска - Binary search tree

Дерево двоичного поиска
Дерево двоичного поиска
Тип	дерево
Изобрел	1960 г.
Изобретенный	PF Windley, AD Бут , AJT Колин , и TN Hibbard
Сложность времени в большой нотации O
Алгоритм
Алгоритм
Космос
Поиск
Вставлять
Удалить

Дерево двоичного поиска размером 9 и глубиной 3 с 8 в корне. Листья не нарисованы.

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

Определение

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

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

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

При вставке или поиске элемента в двоичном дереве поиска ключ каждого посещенного узла должен сравниваться с ключом элемента, который будет вставлен или найден.
Форма двоичного дерева поиска полностью зависит от порядка вставок и удалений и может стать вырожденной.
После длинной перемешанной последовательности случайных вставок и удалений ожидаемая высота дерева приближается к квадратному корню из числа ключей $\sqrt n$ , который растет намного быстрее, чем $log n$ .
Было проведено много исследований, чтобы предотвратить вырождение дерева, приводящее к наихудшей временной сложности $O (n)$ (подробности см. В разделе Типы ).

Отношение заказа

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

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

Операции

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

Searching

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

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

def search_recursively(key, node):
    if node is None or key == node.key:
        return node
    if key < node.key:
        return search_recursively(key, node.left)
    return search_recursively(key, node.right)

Этот же алгоритм можно реализовать итеративно:

def search_iteratively(key, node):
    while node is not None and node.key != key:
        if key < node.key:
            node = node.left
        else:
            node = node.right
    return node

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

struct TreeNode {
  struct TreeNode *child[2];
  int key;
  int value;
} Node;

#define LEFT  0
#define RIGHT 1
#define left  child[LEFT]
#define right child[RIGHT]

#define MAXheight 1024 // BST is possibly unbalanced

struct traverser {
  Node*  nod1;  // current position (NULL,
                //   if nod1->key ahead or behind all nodes of bst)
  int    dir;   // ∈ {LEFT,FOUND,RIGHT}, i.e.
                // == LEFT  <==> position at < nod1
                // == FOUND <==> position at   nod1
                // == RIGHT <==> position at > nod1
  Node** parent = &ancestors[0]; // -> parent of nod1 or NULL if root
  // ancestors[0] == trav->bst->root, if tree not empty.
  Node** limit  = &ancestors[MAXheight]; // -> utmost entry
  BST*   bst;   // -> BST to which this traverser belongs
  Node*  ancestors[MAXheight-1];
};

// search Iteratively with Traverser:
int searchIT (struct traverser* trav, int key) {
  assert (trav != NULL && trav->bst != NULL);
  trav->parent = &(trav->ancestors[-1]);
  dir = LEFT; // in case trav->bst (and while-loop) is empty
  node = trav->bst->root;
  while (node != NULL) {
    if (key == node->key) { // key is in the BST
      trav->node = node; // onto trav
      trav->dir = FOUND;
      // 2 == FOUND: key == node->key
      return node;
    }
    if (key < node->key) dir = LEFT;
    else dir = RIGHT;
    if (++(trav->parent) >= limit) { // stack overflow
      fprintf (stderr, "tree too deep\n");
      exit (EXIT_FAILURE);
    }
    *(trav->parent) = node; // onto stack
    node = node->child[dir];
  }; // end of while-loop
  // *(trav->parent) is the node of closest fit
  trav->dir = dir;
  // 0 == LEFT:  key < (*(trav->parent))->key
  // 1 == RIGHT: key > (*(trav->parent))->key
  return NULL;
}

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

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

Поскольку в худшем случае этот алгоритм должен искать от корня дерева до листа, наиболее удаленного от корня, операция поиска занимает время, пропорциональное высоте дерева (см. Терминологию дерева ). В среднем деревья двоичного поиска с ключами $узлов$ имеют высоту $O (log | Узлы |)$ . Однако в худшем случае деревья двоичного поиска могут иметь высоту $O (| Узлы |)$ , когда несбалансированное дерево напоминает связанный список ( вырожденное дерево ).

Разрешен поиск с дубликатами

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

def search_duplicatesAllowed(key, node):
    new_node = node
    while new_node != None:
        current_node = new_node
        if key < current_node.key:
            dir = 0  # LEFT
        else:  # key >= current_node.key:
            dir = 1  # RIGHT
        new_node = current_node.child[dir]
    return (dir, current_node)

Бинарное дерево рода , оборудованное такой функцией поиска становится стабильной .

Обход

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

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

def inorder_traversal(node, callback):
    if node == None:
        return
    inorder_traversal(node.leftChild, callback)
    callback(node.value)
    inorder_traversal(node.rightChild, callback)

Код для (рекурсивного) обхода порядка в C приведен ниже. В этом случае он будет использовать printfдля печати целочисленного значения узла на экране.

void inorder_traversal(Node *node) {
  if (node == NULL) return;
  inorder_traversal(node->left);
  printf("%i%i ,", node->key, node->value);
  inorder_traversal(node->right);
}

Для каждой формы первого обхода глубины двоичного дерева требуется $2 \times (n -1) \in O (n)$ времени, поскольку он обращается к каждой дуге ровно дважды (один раз вниз, один раз вверх) при посещении каждого узла. Этот алгоритм также $O (n)$ , поэтому он асимптотически оптимален .

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

Переход к следующему или предыдущему узлу

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

Узел, с которого нужно начать, мог быть найден в BST с помощью функции поиска. В следующем примере, в котором не используются родительские указатели, стек указателей на предков был построен, например, searchITфункцией с успешным результатом.

Функция inorderNext возвращает заказовМои-соседа найденного node, либо inorder- SUC cessor (для dir=RIGHT) или inorder- предопределенных cessor (для dir=LEFT), и обновленный stack, так что бинарное дерево поиска может быть последовательно-симметричного пройденного и искали в данное направление в dirдальнейшем.

/* Returns the next or previous data item in inorder within the tree being traversed with trav, or if there are no more data items returns NULL.
In the former case inorderNext() may be called again to retrieve the second next item. */
Node* inorderNext (struct traverser* trav, dir) {
  assert (trav != NULL);
  assert (trav->dir == FOUND);
  assert (dir == LEFT || dir == RIGHT);

  newnode = trav->node->child[dir];
  if (newnode != NULL) {
// Part A: node has a dir-child.
    do {
      node = newnode;
      if (++(trav->parent) > limit) { // stack overflow
        fprintf (stderr, "tree too deep\n");
        exit (EXIT_FAILURE);
      }
      *(trav->parent) = node; // onto stack
      newnode = node->child[1-dir]
    } until (newnode == NULL);
    return node;
  }
// Part B: node does not have a dir-child.
  do {
    if (--(trav->parent) < &(trav->ancestors[0])) // stack is empty
      return NULL;
    oldnode = node;
    node = *(trav->parent); // parent of oldnode
  } until (oldnode != node->child[dir]);
  // now: oldnode == node->child[1-dir], i.e.
  //      node is ancestor (and predecessor for dir==LEFT resp.
  //      successor for dir==RIGHT) of the original trav->node.
  return node;
}

Обратите внимание, что функция не использует ключи, а это означает, что последовательная структура полностью записывается дугами двоичного дерева поиска. Для обходов без изменения направления средняя ( амортизированная ) сложность заключается в том, что полный обход требует шагов для BST размера 1 шаг для дуги вверх и 1 для дуги вниз. Сложность наихудший случай с как высота дерева. ${\ displaystyle {\ mathcal {O}} (1),}$ ${\ displaystyle 2n-2}$ ${\ displaystyle n,}$ ${\ Displaystyle {\ mathcal {O}} (ч)}$ ${\ displaystyle h}$

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

Проверка

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

Свойство BST - каждый узел в правом поддереве должен быть больше текущего узла, а каждый узел в левом поддереве должен быть меньше текущего узла - является ключом к выяснению того, является ли дерево BST или нет. Жадный алгоритм -Просто обхода дерева, на каждом узле проверки содержит ли узел значение больше , чем значение в левом ребенка и меньше , чем значение на правом ребенка не работает для всех случаев. Рассмотрим следующее дерево:

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

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

Итак, условие, которое нам нужно проверить на каждом узле:

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

Рекурсивное решение на C ++ может объяснить это дальше:

struct TreeNode {
    int key;
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
};

bool isBST(struct TreeNode *node, int minKey, int maxKey) {
    if (node == NULL) return true;
    if (node->key < minKey || node->key > maxKey) return false;
    
    return isBST(node->left, minKey, node->key−1) && isBST(node->right, node->key+1, maxKey);
}

node->key+1и node->key−1сделаны, чтобы разрешить только отдельные элементы в BST.

Если мы хотим, чтобы присутствовали одни и те же элементы, то мы можем использовать только node->keyв обоих местах.

Первоначальный вызов этой функции может быть примерно таким:

if (isBST(root, INT_MIN, INT_MAX)) {
    puts("This is a BST.");
} else {
    puts("This is NOT a BST!");
}

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

Как указано в разделе #Traversal , обход двоичного дерева поиска в порядке очередности возвращает отсортированные узлы. Таким образом, нам нужно только сохранить последний посещенный узел при обходе дерева и проверить, меньше ли его ключ (или меньше / равен, если в дереве разрешены дубликаты) по сравнению с текущим ключом.

Вставка

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

Вот как может выполняться типичная вставка двоичного дерева поиска в двоичное дерево в C ++ :

void insert(Node*& root, int key, int value) {
  if (!root) 
    root = new Node(key, value);
  else if (key == root->key)
    root->value = value;
  else if (key < root->key)
    insert(root->left, key, value);
  else  // key > root->key
    insert(root->right, key, value);
}

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

void insert(Node** root, int key, int value) {
  Node **walk = root;
  while (*walk) { 
    int curkey = (*walk)->key;
    if (curkey == key) {
      (*walk)->value = value;
      return;
    }
    if (key > curkey) 
      walk = &(*walk)->right;
    else 
      walk = &(*walk)->left;
  }
  *walk = new Node(key, value);
}

В следующем примере, который не использует родительские указатели, стек указателей на предок было построено , например , с помощью searchITфункции с итоговым ключом node->keyне FOUND.

// insert after search Iteratively with Traverser:
void insertIT(struct traverser* trav,Node* node) {
  assert (trav != NULL);
  assert (trav->node != NULL);
  assert (trav->dir == LEFT || trav->dir == RIGHT);
  assert (node != NULL);
  trav->node->child[trav->dir] = node;
  if (++(trav->parent) > limit) { // stack overflow
    fprintf (stderr, "tree too deep\n");
    exit (EXIT_FAILURE);
  }
  *(trav->parent) = node; // onto stack
}

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

def binary_tree_insert(node, key, value):
    if node == None:
        return NodeTree(None, key, value, None)
    if key == node.key:
        return NodeTree(node.left, key, value, node.right)
    if key < node.key:
        return NodeTree(binary_tree_insert(node.left, key, value), node.key, node.value, node.right)
    return NodeTree(node.left, node.key, node.value, binary_tree_insert(node.right, key, value))

Перестраиваемая часть использует пространство $O (log n)$ в среднем случае и $O (n)$ в худшем случае.

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

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

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

Удаление

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

Удаление узла без дочерних узлов: просто удалите узел из дерева.
Удаление узла с одним дочерним элементом: удалите узел и замените его дочерним.
Удаление узла D с двумя дочерними элементами : выберите либо предшественника D в порядке, либо преемника E (см. Рисунок). Вместо удаления D , перезаписать его ключ и значение с E «с. Если E не имеет дочернего элемента, удалите E из его предыдущего родительского элемента G ; если E есть ребенок F , это право ребенка, так что он должен заменить Е на G .

Удаление узла D с двумя дочерними элементами из двоичного дерева поиска. Сначала идентифицируется крайний левый узел в правом поддереве, последователь E по порядку . Его значение копируется в удаляемый узел D. Затем последователь неупорядочения может быть легко удален, потому что он имеет не более одного дочернего элемента (который в общем случае несбалансированной системы может быть поддеревом).
Же метод работает симметрично с использованием симметричного предшественника C .

Во всех случаях, когда D является корневым, снова сделайте замену корневого узла.

Узлы с двумя дочерними элементами (случай 3) удалить сложнее (см. Рисунок). Последователь в порядке неупорядоченности узла D - это крайний левый дочерний элемент правого поддерева, скажем E , а предшественник узла в порядке следования - самый правый дочерний элемент левого поддерева, скажем , C. В любом случае такой узел E или C не будет иметь левого соотв. правый дочерний элемент, поэтому его можно удалить в соответствии с одним из двух более простых случаев 1 или 2 выше.

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

Анализ во время выполнения: хотя эта операция не всегда проходит по дереву до листа, это всегда возможно; таким образом, в худшем случае требуется время, пропорциональное высоте дерева. Он не требует большего, даже если у узла есть два дочерних узла, поскольку он по-прежнему следует по единственному пути и не посещает ни один узел дважды.

def find_min(self):
    """Get minimum node in a subtree."""
    current_node = self
    while current_node.left_child:
        current_node = current_node.left_child
    return current_node

def replace_node_in_parent(self, new_value=None) -> None:
    if self.parent:
        if self == self.parent.left_child:
            self.parent.left_child = new_value
        else:
            self.parent.right_child = new_value
    if new_value:
        new_value.parent = self.parent

def binary_tree_delete(self, key) -> None:
    if key < self.key:
        self.left_child.binary_tree_delete(key)
        return
    if key > self.key:
        self.right_child.binary_tree_delete(key)
        return
    # Delete the key here
    if self.left_child and self.right_child:  # If both children are present
        successor = self.right_child.find_min()
        self.key = successor.key
        successor.binary_tree_delete(successor.key)
    elif self.left_child:  # If the node has only a *left* child
        self.replace_node_in_parent(self.left_child)
    elif self.right_child:  # If the node has only a *right* child
        self.replace_node_in_parent(self.right_child)
    else:
        self.replace_node_in_parent(None)  # This node has no children

Параллельные алгоритмы

Существуют также параллельные алгоритмы для двоичных деревьев поиска, включая вставку / удаление нескольких элементов, построение из массива, фильтрацию с определенным предиктором, сглаживание в массив, слияние / вычитание / пересечение двух деревьев и т. Д. Эти алгоритмы могут быть реализованы с использованием основанных на объединении древовидные алгоритмы , которые также могут поддерживать балансировку дерева с помощью нескольких схем балансировки (включая AVL-дерево , красно-черное дерево , сбалансированное по весу дерево и treap ).

Примеры приложений

Сортировать

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

Наихудшее время build_binary_tree- $O (n 2) -$ если вы скармливаете ему отсортированный список значений, он объединяет их в связанный список без левых поддеревьев. Например, build_binary_tree([1, 2, 3, 4, 5])дает дерево (1 (2 (3 (4 (5))))).

Существует несколько схем преодоления этого недостатка с помощью простых бинарных деревьев; наиболее распространенным является самобалансирующееся двоичное дерево поиска . Если эта же процедура выполняется с использованием такого дерева, общее время наихудшего случая составляет $O (n log n)$ , что является асимптотически оптимальным для сортировки сравнения . На практике дополнительные накладные расходы во времени и пространстве для сортировки на основе дерева (особенно для распределения узлов ) делают ее хуже по сравнению с другими асимптотически оптимальными сортировками, такими как heapsort для сортировки статических списков. С другой стороны, это один из наиболее эффективных методов инкрементной сортировки , когда элементы добавляются в список с течением времени, при этом список всегда остается отсортированным.

Приоритетные операции с очередью

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

// Precondition: T is not a leaf
function find-min(T):
    while hasLeft(T):
        T ? left(T)
    return key(T)

Find-max аналогичен: следуйте правым указателям, насколько это возможно. Delete-min ( max ) может просто найти минимум (максимум), а затем удалить его. Таким образом, и вставка, и удаление занимают логарифмическое время, как и в двоичной куче , но в отличие от двоичной кучи и большинства других реализаций приоритетной очереди, одно дерево может поддерживать все find-min , find-max , delete-min. и delete-max одновременно, делая деревья двоичного поиска подходящими в качестве двусторонних очередей приоритетов .

Типы

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

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

Сравнение производительности

DA Heger (2004) представил сравнение производительности деревьев двоичного поиска. Было обнаружено, что Treap имеет лучшую среднюю производительность, в то время как у красно-черного дерева наименьшее количество вариаций производительности.

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

Поворот дерева - это очень распространенная внутренняя операция в бинарных деревьях для поддержания идеального или почти идеального внутреннего баланса в дереве.

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

Даже если у нас есть только оценки затрат на поиск, такая система может значительно ускорить поиск в среднем. Например, если у нас есть BST английских слов , используемых в орфографический , мы могли бы уравновесить дерево , основанное на частоте слов в текстовых корпусов , помещая слова , как возле корня и слова , как agerasia вблизи листьев. Такое дерево можно сравнить с деревьями Хаффмана , которые аналогичным образом стремятся разместить часто используемые элементы рядом с корнем, чтобы обеспечить плотное кодирование информации; однако деревья Хаффмана хранят элементы данных только в листьях, и эти элементы не нужно упорядочивать.

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

Алфавитные деревья - это деревья Хаффмана с дополнительным ограничением на порядок или, что то же самое, деревья поиска с модификацией, согласно которой все элементы хранятся в листьях. Существуют более быстрые алгоритмы для оптимальных алфавитно-двоичных деревьев (OABT).

Смотрите также

Примечания

использованная литература

дальнейшее чтение

Эта статья включает материалы, являющиеся общественным достоянием из документа NIST : Блэк, Пол Э. «Дерево двоичного поиска» . Словарь алгоритмов и структур данных .
Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001). «12: деревья двоичного поиска, 15.5: оптимальные деревья двоичного поиска». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 253–272, 356–363. ISBN 0-262-03293-7.
Ярк, Дуэйн Дж. (3 декабря 2005 г.). «Обходы двоичного дерева» . Интерактивные визуализации структуры данных . Университет Мэриленда . Архивировано из оригинального 27 февраля 2014 года . Проверено 30 апреля 2006 года .
Кнут, Дональд (1997). «6.2.2: Поиск двоичного дерева». Искусство программирования . 3: «Сортировка и поиск» (3-е изд.). Эддисон-Уэсли. С. 426–458. ISBN 0-201-89685-0.
Долго, Шон. «Дерево двоичного поиска» ( PPT ) . Визуализация структур данных и алгоритмов - подход на основе слайдов PowerPoint . СУНИ Онеонта .
Парланте, Ник (2001). «Бинарные деревья» . Образовательная библиотека CS . Стэнфордский университет .

внешние ссылки

Бен Пфафф: Введение в деревья двоичного поиска и сбалансированные деревья . (PDF; 1675 kB) 2004 г.
Визуализатор двоичного дерева (JavaScript-анимация различных структур данных на основе BT)

Languages

In other projects