데이터구조 - 트리

트리구조

나뭇가지가 가지를 치며 뻗어나가듯한 모양으로 데이터를 저장하는 방식

나무를 뒤집어 놓은 모양으로 데이터 구조가 저장된다

 

• 명칭
  • 노드 (node) : 트리구조를 형성하는 요소
  • 엣지 (edge) : 노드와 노드를 연결하는 선. 가지(branch)
  • 루트 노드 (root node) : 최상위 노드
  • 리프 노드 (leaf node) : 하위 노드(자식노드)가 없는 최하위 노드
  • 트리 깊이 : 루트노드에서 리프노드까지 거쳐야하는 단계의 개수

 

• 트리구조 종류
  • 이진트리 (binary tree) : 하위 노드 개수가 2개로 제한한 트리구조
  • N항트리 (N-ary tree / N-way tree) : 하위 노드 개수가 3개 이상인 트리구조

 

AVL 트리 (Adelson-Velskii and Landis' tree)

• 루트 노드를 중심으로 좌우 노드의 높이(깊이) 차이가 1 이하인 트리구조를 말한다.
• 즉 높이 차이가 거의 없는 트리구조를 말한다. 
• 좌우 차이가 심한 경우 한쪽으로 비대칭한 구조가 되어 검색 효율성이 떨어진다.
• 이를 좌우높이 차이가 없도록 조정해주면 좀더 효율적인 트리구조로 변경된다.