카샤의 만개시기

이진트리는 한쪽으로 치우친 형태로 트리 구조가 만들어 질수 있는데 그렇게 되면 트리 구조가 아닌 일반적인 연결 리스트와 별 차이가 없게 되기 때문에 이진 트리의 장점이 사라지게 된다. AVL 트리는 이러한 전체 트리의 구조가 균형이 맞도록 하는 트리다. 즉, 쏠린 트리처럼 트리 구조가 한쪽으로 쏠리는 것을 막아 트리 구조의 균형을 맞춤으로써 조회 성능을 O(logN)으로 유지할수 있는것이다. AVL 트리는 다음과 같은 특징이 있다. 균형도(Balance Factor)라는 개념이 있는데, 이는 각 노드의 왼쪽 노드와 오른쪽 노드의 차이를 말한다. 리프 노드의 균형도는 0이다. 균형도는 '왼쪽 자식 트리의 높이 - 오른쪽 자식 트리의 높이'로 계산한다. 왼쪽 자식 노드와 오른쪽 자식 노드의 균..