Докажите, что это предположение не работает для всех деревьев двоичного поиска.

Question

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

У меня есть теория, которую я хочу опровергнуть. В нем говорится, что для любого двоичного дерева, если мы возьмем путь поиска (назовем его S) к листовому узлу, то любой узел на LEFT из S должен быть меньше любого узла на S, и любой узел RIGHT должен быть больше любого узла на S. Другими словами: узел слева < узел на S < узел справа. Есть ли какой-либо контрпример, чтобы опровергнуть эту теорию?

For example if we have this tree:

поиска пути для узла K будет М-> Р-> Н-> K

Множество узлов слева содержит C, A, D, G

Набор справа содержит V, S, P, T, X, W

Что такое хороший пример счетчика?

спасибо.

Answer 1

Это не совсем ответ, но это не будет вписываться в комментарии ...

Я думаю, что ваше определение «бинарное дерево поиска» немного не хватает - в конце концов, это будет ОТВЕЧАТЬ ВАШИМ определение:

B 
    \ 
    C 
    /\ 
    A D 

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

Возможно, более точное определение поможет вам подумать о вашей «теории».