[멋쟁이사자처럼 유니티 TIL] 2024_12_10(화) 강의 요약 및 정리(1)

자료구조: 트리 (Tree)

계층적 구조를 표현하는 비선형 자료구조. 노드들과 노드들을 연결하는 간선들로 구성되어 있음.

 

트리의 구조와 용어

트리 구조를 더 자세히 이해하기 위해 주요 용어와 개념을 살펴보겠습니다:

• 노드 (Node): 트리를 구성하는 기본 요소로, 데이터를 저장합니다.
• 간선 (Edge): 노드와 노드를 연결하는 선입니다.
• 루트 노드 (Root Node): 트리의 최상위에 있는 노드입니다.
• 부모 노드 (Parent Node): 직접적인 상위 노드를 의미합니다.
• 자식 노드 (Child Node): 직접적인 하위 노드를 의미합니다.
• 리프 노드 (Leaf Node): 자식이 없는 노드로, 트리의 끝단에 위치합니다.
• 깊이 (Depth): 루트에서 특정 노드까지의 경로 길이입니다.
• 높이 (Height): 노드에서 가장 먼 리프까지의 경로 길이입니다.

트리의 주요 특징:

• 하나의 루트 노드를 가집니다.
• 각 노드는 0개 이상의 자식 노드를 가질 수 있습니다.
• 사이클이 존재하지 않습니다.

트리는 구조와 특성에 따라 다양한 종류가 있습니다:

• 일반 트리 (General Tree): 노드가 임의의 수의 자식을 가질 수 있는 트리입니다.
• 이진 트리 (Binary Tree): 각 노드가 최대 2개의 자식을 가질 수 있는 트리입니다.

• 완전 이진 트리 (Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워진 이진 트리입니다.
• 포화 이진 트리 (Perfect Binary Tree): 모든 내부 노드가 2개의 자식을 가지며, 모든 리프 노드가 같은 레벨에 있는 트리입니다.
• 이진 탐색 트리 (Binary Search Tree): 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가지는 이진 트리입니다.
• AVL 트리: 자동으로 균형을 맞추는 이진 탐색 트리로, 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1입니다.
• 레드-블랙 트리 (Red-Black Tree): 자가 균형 이진 탐색 트리의 일종으로, 색상 속성을 사용하여 균형을 유지합니다.

트리의 순회 방법

트리 순회는 트리의 모든 노드를 체계적으로 방문하는 프로세스입니다. 주요 순회 방법은 다음과 같습니다:

• 전위 순회 (Preorder): 루트 → 왼쪽 서브트리 → 오른쪽 서브트리

• 후위 순회 (Postorder): 왼쪽 서브트리 → 오른쪽 서브트리 → 루트

 

• 중위 순회 (Inorder): 왼쪽 서브트리 → 루트 → 오른쪽 서브트리

 

 

Left = Right = null;

// Left와 Right를 null로 초기화하여, 노드가 처음 생성될 때는 자식 노드가 없음을 의미

 

private Node root;

// root는 트리의 최상위 노드를 참조. 이 변수는 트리의 시작점이자 첫 번째 노드로 사용

트리를 구현할 때, 루트 노드를 통해 모든 다른 노드들에 접근하거나 트리 구조를 변경할 수 있음.

 

 

 

 

- PreOrder(root) 로 출력시 :

  // "전위 순회 : 100 50 40 60 110 70 323

- PostOrder(root) 로 출력시 :

  // "호위 순회 : 40 60 50 70 323 110 100

- InOrder(root) 로 출력시 :

  // "중위 순회 : 40 50 60 100 70 110 323