Разница между двоичным деревом и двоичным деревом поиска

Question

Может ли кто-нибудь объяснить разницу между двоичным деревом и бинарным деревом поиска на примере ?

Answer 1

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

  1
 / \
2   3

---

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

  2
 / \
1   3

Answer 2

Двоичное дерево - это специализированная форма дерева с двумя дочерними элементами (левым дочерним элементом и правым дочерним элементом).Это просто представление данных в древовидной структуре

Двоичное дерево поиска (BST) - это особый тип двоичного дерева, который соответствует следующему условию:

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

Answer 3

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

Бинарное дерево поиска (BST) или «упорядоченное бинарное дерево» - это тип бинарного дерева, в котором узлы расположены по порядку: для каждого узла все элементы в его левом поддереве меньше узел (<), и все элементы в его правом поддереве больше, чем узел (>).

    5
   / \
  3   6 
 / \   \
1   4   9    

Показанное выше дерево является двоичным деревом поиска - «корневым» узлом является 5, а его левые узлы поддеревьев (1, 3, 4) меньше 5, а его правые узлы поддеревьев (6, 9) > 5. Рекурсивно, каждое из поддеревьев должно также подчиняться ограничению бинарного дерева поиска: в поддереве (1, 3, 4) корень 3, 1 <3 и 4> 3.

Не упустите точную формулировку в задачах - «двоичное дерево поиска» отличается от «двоичного дерева».

Answer 4

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

boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max)
{

    if(node == null)
    {
        return true;
    }

    boolean left = isBinarySearchTree(node.getLeft(), min, node.getValue());
    boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

    return left && right && (node.getValue()<max) && (node.getValue()>=min);

}

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

Answer 5

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

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

Таким образом, все BST имеют значение Бинарное дерево , но только некоторые Бинарное дерево могут быть также BST .Обратите внимание, что BST является подмножеством Binary Tree .

Итак, Binary Tree является более общей структурой данных, чем Двоичное дерево поиска .А также вы должны уведомить, что Двоичное дерево поиска является отсортированным деревом, тогда как для общего Двоичного дерева .

* 1048 такого набора нет.* Двоичное дерево

A Binary Tree, которое не a BST;

         5
       /   \
      /     \
     9       2
    / \     / \
  15   17  19  21

Двоичное дерево поиска (отсортированное дерево)

A Двоичное дерево поиска , которое также является Двоичным деревом ;

         50
       /    \
      /      \
     25      75
    /  \    /  \
  20    30 70   80

Свойство узла бинарного дерева поиска

Также сообщите об этом для любого родительский узел в BST ;

• Все левые узлы имеют меньшее значение, чем значение родительского узла.В верхнем примере узлы со значениями {20, 25, 30}, которые все расположены слева ( левые потомки ) из 50, меньше 50.

• Все правые узлы имеют большее значение, чем значение родительского узла.В верхнем примере узлы со значениями {70, 75, 80}, которые все расположены справа ( правые потомки ) из 50, больше 50.

Нет такого правила для Двоичное дерево Узел.Единственное правило для Binary Tree Node - это наличие двух дочерних элементов, поэтому само собой объясняется, почему он называется binary .

Answer 6

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

Answer 7

Двоичное дерево

Двоичное дерево может быть чем угодно , которое имеет 2 дочерних и 1 родительский Это может быть реализовано в виде связанного списка или массива, или с вашим пользовательским API. Как только вы начинаете добавлять в него более конкретные правила, оно становится более специализированным деревом . Наиболее распространенная известная реализация состоит в том, что добавьте меньшие узлы слева и более крупные справа.

Например, помеченное двоичное дерево размером 9 и высотой 3 с корневым узлом со значением 2. Дерево несбалансировано и не отсортировано . https://en.wikipedia.org/wiki/Binary_tree

Например, в дереве слева у A есть 6 детей {B, C, D, E, F, G}. Его можно преобразовать в двоичное дерево справа.

Бинарный поиск

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

Двоичный поиск сравнивает целевое значение с средним элементом массива; если они неравны, половина, в которой цель не может находиться, удаляется, и поиск продолжается на оставшейся половине, пока она не будет успешной или оставшаяся половина не станет пустой. https://en.wikipedia.org/wiki/Binary_search_algorithm

Дерево, представляющее бинарный поиск . Здесь ищется массив [20, 30, 40, 50, 90, 100], а целевое значение - 40.

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

Это одна из реализаций двоичного дерева. Это специализировано для поиска .

Бинарное дерево поиска и структуры данных B-дерева основаны на бинарный поиск .

Двоичные деревья поиска (BST), иногда называемые упорядоченными или отсортированными двоичными деревьями, представляют собой определенный тип контейнера : структуры данных, которые хранят «элементы» (такие как числа, имена и т. Д.) В памяти. https://en.wikipedia.org/wiki/Binary_search_tree

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

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

Изображение взято из Алгоритмы (4-е издание)

Answer 8

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

Answer 9

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

Answer 10

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

Пересечение дерева в Inorder Fashion (т.е. Левый ребенок -> Родитель -> Правый ребенок), Сохраняйте данные пройденного узла во временной переменной, скажем, temp , непосредственно перед сохранением в temp . Проверьте, выше ли данные текущего узла, чем у предыдущего, или нет. Тогда просто сломайте его, дерево не является бинарным поисковым деревом, иначе проходите до конца.

Ниже приведен пример с Java:

public static boolean isBinarySearchTree(Tree root)
{
    if(root==null)
        return false;

    isBinarySearchTree(root.left);
    if(tree.data<temp)
        return false;
    else
        temp=tree.data;
    isBinarySearchTree(root.right);
    return true;
}

Сохранить временную переменную снаружи