Редактировать
Если подумать, я более склонен полагать, что в вашем примере есть опечатка, а не BST. Расположение 10 не имеет смысла. Вплоть до тех пор это совершенно действительный BST. Если бы 10 были вставлены в качестве левого листа узла 12, тогда BST-сущность была бы сохранена.
Если leftNode.value < value <= rightNode.value применяется только к непосредственным потомкам, а не ко всем потомкам, то это бесполезная структура данных. Я имею в виду, я думаю, что его можно использовать, но, поскольку вы в конечном итоге пройдете по всему дереву как при вставках, так и при поиске, это кажется довольно бессмысленным.
Я думаю, что схема вашего алгоритма вставки будет выглядеть следующим образом: псевдопифон. Суть в том, чтобы попытаться добавить узел в виде листа, где это возможно, или вставить его в любое поддерево. Влево или вправо, это не имеет значения.
По сути, мы просто смотрим вниз по всему дереву, где новое значение может быть добавлено как листовой узел. Как вы говорите, критерий порядка относится только к непосредственным детям. Вы должны быть придирчивы к добавлению новых листовых узлов. Но вы пробуете левое и правое поддеревья без разбора.
class TreeNode:
def insert(self, value):
# Can we add it as the left leaf of this node?
if self.left is None and value < self.value:
self.left = TreeNode(value)
return True
# Can we add it as the right leaf of this node?
if self.right is None and value >= self.value:
self.right = TreeNode(value)
return True
# Can we add it somewhere down the left sub-tree?
if self.left.insert(value):
return True
# Can we add it somewhere down the right sub-tree?
if self.right.insert(value):
return True
# Didn't find anywhere to add the node.
return False
Полагаю, тут становится сложно, если вам нужно попытаться сбалансировать поддеревья, а не просто случайно вставить новые узлы в любой произвольной точке дерева. Если это проблема, вы можете изменить приведенный выше алгоритм так, чтобы он вставлялся в самой мелкой точке.
Представьте, что существует метод insert_depth, который возвращает глубину, в которую узел будет вставлен на , если он был вставлен в определенное поддерево, или возвращает & infin; если вставка невозможна. Опять же, это просто псевдокод:
left_depth = self.left .insert_depth(value)
right_depth = self.right.insert_depth(value)
if left_depth < right_depth:
return self.left .insert(value)
else:
return self.right.insert(value)
В реальном коде я бы написал "если бы вы собирались вставить узел, куда бы вы его вставили?" вспомогательный метод. Запустите этот метод для обоих поддеревьев, сравните точки вставки и выберите одну (т.е. самую мелкую). Код будет немного неловким, но он избавит вас от обхода каждого поддерева дважды.