Двоичные поисковые деревья

Question

Это некоторый код, найденный в Википедии относительно BST:

# 'node' refers to the parent-node in this case
 def search_binary_tree(node, key):
     if node is None:
         return None  # key not found
     if key < node.key:
         return search_binary_tree(node.leftChild, key)
     elif key > node.key:
         return search_binary_tree(node.rightChild, key)
     else:  # key is equal to node key
         return node.value  # found key

Теперь вот бинарное дерево:

       10
    5        12
  3   8    9   14
     4 11  

Если я ищу 11, и я следую алгоритму вверхтам я начинаю с 10, я иду вправо до 12, а затем налево до 9. И я достигаю конца дерева, не найдя 11. Но в моем дереве есть 11, это просто на другой стороне.

Не могли бы вы объяснить, каковы ограничения в двоичном дереве для этого алгоритма, чтобы работать на моем дереве?

Спасибо.

Answer 1

Это просто потому, что ваше дерево не является двоичным деревом поиска: оно не упорядочено правильно. BST строится так, как описано в алгоритме. Например, в вашем дереве: узел «9» находится не в правильном положении, поскольку при 9 <10 он должен находиться под левой ветвью вашего корневого узла «10». То же самое для «14» и «11», которые должны быть на правой ветви. </p>

например, BST может что-то вроде этого:

    10
  5    11
3   8    12
          14

Answer 2

Дерево, которое вы представили не в BST.11 и 14 никогда бы не были вставлены слева от 10, и поэтому алгоритм там не ищет.9 также неуместен.

Вставка в соответствии с Википедией:

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

Вы можете сказать, что двоичное дерево является BST, если оно имеет следующие свойства (также из Википедии):

1. Левое поддерево узла содержит только узлы с ключами, меньшими, чемключ узла.
2. Правое поддерево узла содержит только узлы с ключами, которые больше ключа узла.
3. И левое, и правое поддеревья также должны быть двоичными деревьями поиска.

Answer 3

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

Принимая во внимание, что приведенный вами пример - это просто двоичное дерево, а не двоичное дерево поиска. Вы можете видеть, что значения 11 и 14 оставлены родительскому узлу 10, который нарушает свойство BST. Взгляните здесь для бинарных деревьев поиска.

Answer 4

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

Answer 5

Вы разместили узлы 14 и 11 в неправильном месте.Из статьи Википедии о BST :

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

Как вы можете видетьи 14, и 11 больше 8.