균형 이진 검색 트리의 정의

Question

그래서 균형 이진 검색 트리에 대해 연구했습니다.

내가 봤 한

, 이것은 내가 발견 한 것입니다 :

모든 노드의 두 개의 하위 트리의 깊이가 (위키 백과) 1 이하로 차이가있는 이진 트리

수 균형 이진 트리를 단지 ceil (log (n + 1)/log 2) 이상의 높이를 갖는 트리로 정의하지 않을 것인가?

그리고 대답은 Is Binary Search tree balanced? 인 것 같습니다. 질문자는 이미 똑같은 질문을 한 것 같지만, 받아 들인 대답은 피보나치 나무의 예를 들어서 그 아이디어를 거부합니다. 피보나치 나무는 균형 잡힌 나무가 아닙니까? 응답자가 AVL 트리의 균형 잡힌 트리의 정의와 혼동을 일으킬 수 있다고 생각합니다. 내 이해에 따라 특정 불균형 트리를 허용합니다.

Answer 1

내 계산이 잘못되지 않으면 정의가 작동하지 않습니다. 예를 들어 높이 6의 전체 이진 트리를 가져 가면 노드는 63 개가됩니다. 맨 아래쪽에있는 형제 두 명과 부모를 제거하면 노드가 60 개가됩니다. 이 트리는 균형이 맞지 않지만 높이는 여전히 ceil과 같습니다 (log (n + 1)/log 2).