[일반] 트리 관련 질문…

[익명(118.235)]

노드 n개짜리 임의의 BST의 height = O(logN) 이다

위 명제가 참인데, 그 역은 거짓이라고 배움

이 역의 반례가 너무나도 궁금함….

[익명(58.228)]

https://csacademy.com/app/graph_editor/여기
들어가서 123456781 21 31 43 52 74 67 8넣어보세요

[익명(58.228)]

어 뭐야

[익명(58.228)]

https://imgur.com/a/UxkABnK

[익명(58.228)]

다음 트리는 정점 8개, 깊이는 3 = log2 8이지만 BST가 아닙니다

[익명(118.235)]

감사합니다! 그리고.. 제가 질문을 약간 잘못적었는데, binary tree 라는 전제를 빼먹었습니다. height가 O(logN)인 binary tree가 not balanced 인 예시를 찾고있습니다.

[익명(61.101)]

perfect binary tree에서 아무 leaf 골라서 그 부모랑 그 나머지 자식이랑 세개 지우면 됨

[익명(61.74)]

감사합니다! 신기하네요… 이런건 직관적으로 떠오르는건가요 아님 유도하신건가요?