Binary tree search

Информация

Бинарное дерево (Binary Tree) - это дерево, в котором у каждого узла не более двух дочерних элементов, обычно называемых левым и правым дочерним элементами. В бинарном дереве каждый узел может иметь от 0 до 2 дочерних узлов.

Бинарное дерево поиска (Binary Search Tree) - это бинарное дерево, в котором для всех узлов, лежащих в левом поддереве, значения этих узлов меньше, чем значение корня, а для всех узлов, лежащих в правом поддереве, значения этих узлов больше, чем значение корня.

Отличие от Binary tree

Отличия:

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