Вопрос о бинарных поисковых деревьях

Question

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

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

Спасибо.

Answer 1

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

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

И если вы чувствуете себя особенно предприимчивым, возьмите массив и импортируйте его в виде дерева. Для этого существует специальный формат, который выглядит примерно так (1 (2 (3)), (5) - этот пример не сбалансирован, но вы поняли идею, и он есть в Википедии.

Answer 2

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

Answer 3

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

Мое искусство ASCII не велико, но вращение может превратить это дерево:

        f
    d       g
  b   e           
 a c

в это дерево:

        d
    b       f
  a   c   e   g

Второе сбалансированное дерево сделает поиск f и g медленнее, а поиск d, a, b, c быстрее, если e останется прежним.

Answer 4

Мне кажется, я где-то видел "карту" операции. При изменении всех элементов дерева с монотонной функцией. То есть функция со свойством всегда подниматься (f (x + dx)> = f (x)) или всегда опускаться (f (x + dx) <= f (x)). В одном случае вам нужно будет применить эту функцию к каждому узлу в другом, вам также потребуется зеркально отобразить дерево (поменять местами «левый» и «правый» узлы), поскольку порядок получаемых значений будет обратным. </p>

Answer 5

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

1. Обратный порядок всего в дереве. Это O (N) я думаю?
2. Поддерево, элементы между x и y как само двоичное дерево поиска - должно быть O (log N), я думаю?
3. Минимум, максимум? Да, тривиально, но у меня нет идей!

Answer 6

Если это домашнее задание, удачи!

Если это любопытно, веселитесь!

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

http://www.boost.org/doc/libs/1_38_0/boost/graph/detail/array_binary_tree.hpp

Answer 7

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