이 가정은 모든 이진 탐색 트리에 대해 작동하지 않음을 증명하십시오.

Question

(이진 탐색 트리는 각 노드가 두 개의 자식을 가질 수있는 이진 트리입니다. 오른쪽이 노드보다 크고 왼쪽이 노드보다 작아야합니다. .)

나는 반증하고 싶은 이론이있다. 그것은 모든 이진 트리에 대해 우리가 리프 노드에 검색 경로 (S로 부름)를 취하면 S의 왼쪽에있는 노드는 S의 노드보다 작아야하며 RIGHT의 노드는 다른 말로하면 : 왼쪽에있는 노드 < 노드 오른쪽에 S < 노드가 있습니다. 이 이론을 반증 할 수있는 반례문이 있습니까?

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 

그러나 진정한 이진 검색 트리가 아닙니다. 정의에 재귀 관계가 없습니다. 이진 탐색 트리에서 노드의 왼쪽 하위 트리에있는 모든 요소는 노드 레이블보다 작고 오른쪽 하위 트리의 모든 요소는 즉각적인 자식뿐만 아니라 더 큽니다.

아마 더 정확한 정의를 갖는 것이 당신의 "이론"에 대해 생각하는 데 도움이 될 것입니다.