이진 트리의 문제점이진 트리의 경우 균형이 잡혀있다면 삽입, 삭제, 검색을 할 때 O(logn)의 시간 복잡도를 기대할 수 있지만, 한 쪽으로 편향되어 있다면 선형 자료구조처럼 작동해 O(n)의 시간 복잡도를 가지게 된다.그러므로 이진 트리의 균형을 맞추는 것은 중요하다.  AVL 트리AVL 트리는 스스로 균형을 잡는 자가 균형 이진 탐색 트리이다.어떤 노드의 두 자식 서브트리의 높이의 차이가 최대 1만큼만 차이난다.어떤 시점에서 높이 차이가 1보다 커지면 균형이 무너졌다고 판단해 회전을 통해 스스로 균형을 잡는다.검색, 삽입, 삭제는 평균과 최악의 경우 모두 O(log n)의 시간 복잡도가 걸린다.Balance FactorAVL 트리에서 균형의 무너짐을 판단하는 기준이다.Balance Factor 계산..

트리 (Tree)트리의 정의트리는 한 개 이상의 노드로 이루어진 유한 집합으로서노드 중에는 루트(root)라고 하는 노드가 하나 있고나머지 노드들은 n개의 분리 집합 T1, T2, ..., Tn으로 분할 될 수 있다. 이때, 분리 집합 T1, T2, ..., Tn은 각각 하나의 트리이며 루트의 서브트리라고 한다.트리의 구조 및 용어트리 용어차수(degree): 어떤 노드의 자식 개수리프(leaf) 또는 단말(terminal) 노드: 차수가 0인 노드자식(children): 어떤 노드 X의 서브트리의 루트들부모(parent): 어떤 노드 X형제(sibling): 부모가 같은 자식들트리의 차수(degree of tree): 그 트리에 있는 노드의 최대 차수조상(ancestor): 루트에서 그 노드까지의 경로..