비선형 자료구조

노드와 링크로 구성도니 자료구조 (그래프의 일종, Cycle 없음)계층적 구조를 나타낼 때 사용ex) 폴더구조 (디렉토리, 서브디렉토리)ex) 조직도, 가계도, ...tree노드(Node): 트리구조의 자료값을 담고있는 단위에지(Edge): 노드 간의 연결선(link,

왼쪽 자식노드의 키는 부모 노드의 키보다 작음오른쪽 자식 노드의 키는 부모 노드의 키보다 큼각각의 서브 트리도 이진 탐색 트리를 유지중복된 키를 허용하지 않음bst데이터가 잘 정렬됨이진트리에 비해 탐색 빠름 (균형 유지가 필요) \- 균형상태: $O(logn)$ \

노드가 삽입, 삭제될 떄 트리의 균형을 체크하고 유지하는 트리각 노드의 BF를 -1, 0 ,1 만 가지게 하여 균형을 유지BF(Balnce Factor)왼쪽 서브트리 높이 - 오른쪽 서브트리 높이avl균형이 깨진 경우, BF가 +이면 왼쪽 서브트리에 이상이 있음균형이