1. AVL트리 만드려고 적정 이진트리(연결리스트 사용)를 생성하려고함.

2 적정 이진트리 생성 완료.(높이값 넣는것 제외)

3. 근데 높이값을 넣어야하는데 문제 발생.


문제점:  find + insert 모두 O(log n) 시간에 가능한데 높이값을 넣는게 문제. 중위, 선위, 후위순회 무슨 순회를 하던 결국에는  n개의 노드에 접근해서 높이값을 넣어줘야 하기 때문에 O(n)시간이 걸려서 전체적인 실행 시간은 O(n)시간이 되어버림.

이러면 그냥 높이값 안넣고 일반 이진트리가 O(n)시간걸리는거랑 똑같이됨. 


높이를 어떻게 삽입해야 O(log n) 시간에 가능함?