Tree

Tree

계층적 구조를 가지는 자료구조, 부모-자식 관계로 노드가 연결됨

Tree terminology

• Root: 트리의 최상위 노드, 트리의 시작점
• Leaf: 자식 노드가 없는 노드
• Parent: 특정 노드를 포함하는 상위 노드
• Children: 특정 노드가 포함하고 있는 하위 노드들
• Subtree: 트리의 부분 구조로, 특정 노드를 루트로 하는 트리
• Level: 루트에서 떨어진 거리(깊이), 간선으로 깊이를 셈
• Height: 트리의 최하위 레벨

Type of tree

• General Tree
  모든 노드가 자식 노드를 임의 개수만큼 가지는 기본적인 트리
• Binary Tree
  각 노드가 최대 두 개의 자식을 가질 수 있는 트리
• Complete Binary Tree
  마지막 레벨의 위 레벨은 완전히 채워지고, 마지막 레벨은 왼쪽부터 채워진 트리
• Full Binary Tree
  모든 노드가 0개 또느 2개의 자식을 가지는 이진 트리, 이상적인 트리
• Binary Search Tree, BST
  이진 트리의 일종, 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 이진 트리
• Balanced Binary Tree
  모든 서브트리의 높이 차이가 일정 범위 내로 제한된 트리, 삽입과 삭제 후에도 균형을 유지되도록 설계된 트리
• AVL Tree
  이진 탐색 트리의 일종, 모든 노드의 두 서브트리의 높이 차이가 1을 넘지 않도록 유지하는 균형 트리
• Red-Black Tree
  이진 탐색 트리의 변형, 노드를 빨간색과 검은 색으로 색칠하여 트리의 균형을 유지
• N-ary Tree
  각 노드가 최대 N개의 자식을 가질 수 있는 트리
• B- Tree
  균형을 유지하는 다진 트리
• B+ Tree
  B- Tree의 변형으로 모든 리프 노트에 데이터를 저장하며, 리프 노드가 서로 연결되어 있어 range query가 효율적
• Trie, Prefix Tree
  문자열을 효율적으로 저장하고 탐색할 수 있는 트리 구조, 문자열의 접두사를 공유하는 형태로 구성됨
• Heap
  완전 이진 트리 기반의 트리, 최댓값이나 최솟값을 빠르게 찾기 위해 설계된 트리

Types of trees to study

• Binary Search Tree, BST
• AVL Tree
• Red-Black Tree Insertion
• Red-Black Tree Deletion
• Heap
• Trie, Prefix Tree