この仮定は、すべてのバイナリ検索ツリーでは機能しないことを証明してください。

Question

（バイナリ検索ツリーは、各ノードが2つの子atmostを持つことができるバイナリツリーであり、右側はノードより大きく、 。）

私は反証したいという理論を持っています。任意のバイナリツリーで、リーフノードに探索パス（Sと呼ぶ）を取ると、SのLEFT上のノードはS上のどのノードよりも小さくなければならず、RIGHTの任意のノードは言い換えれば、左側のノード<ノード右側のノード<上のノード。この理論を反証する反例はありますか？

For example if we have this tree:

ノードKの検索パスは次のようになりM-> F-> H-> K

左のノードのセットはC、A、D、G

が含ま右のセットには、V、S、P、T、X、Wが含まれています

良いカウンターの例は何ですか？

ありがとうございます。

Answer 1

これは本当に答えではないが、それは私が「二分探索木」のあなたの定義が少し欠けていると思う...コメントに

に合わないだろう - すべての後に、これはあなたに会います定義：

B 
    \ 
    C 
    /\ 
    A D 

しかし、これは真のバイナリ検索ツリーではありません。あなたの定義には再帰的な関係はありません。バイナリ検索ツリーでは、ノードの左のサブツリーのすべての要素がノードのラベルより小さく、右のサブツリーのすべての要素が大きくなります。

おそらくもっと正確な定義を持つことは、あなたの "理論"について考える上で役に立ちます。