고마우미

Tree란?

Root 노드에서 시작해서 여러개의 하위 노드로 이어진다.

이러한 구조는 데이터 계층적이고 효율적으로 관리 할 수 있다.

Tree 용어 정리

[기본정보]

• Node: 트리를 구성하는 기본 단위. 데이터와 다른 노드를 가리키는 포인터를 포함
• Root : 트리의 최상위 노드. 이 노드에서 모든 트리 순회가 시작된다.
• Leaf : 자식노드가 없는 노드. Tree가 나무라면 Leaf는 나뭇잎
• Level : 트리에서 같은 깊이에 있는 노드들의 집합. (ex: root - 1 , root의 자식 - 2 ...)
• Sub Tree : 특정 노드와 그 노드의 모든 자손 노드로 구성된 트리 -> 재귀적 구조

  [특정 노드에 대한 정보]

• Depth: 특정 노드에서 루트 노드까지 도달하기 위한 간선의 수
• Height: 특정 노드에서 가장 멀리 떨어진 리프 노드까지의 "최장 경로" 길이

  [계층적 구조에 대한 용어]

• SubTree:  특정 노드와 그 노드의 모든 자손 노드로 구성된 트리
• Parent :  루트 노드를 제외 한 노드는 반드시 한명의 부모를 갖습니다.
• Child: 부모 노드에 연결된 하위 노드
• Sibling : 같은 레벨에 있는 노드

중요한 Tree 종류

Binary Tree 각 노드가 최대 2개의 자식 노드를 가지는 트리

• Full Binary Tree : 모든 레벨이 완전히 채워져 있음
• Complete Binary Tree : 마지막 레벨을 제외한 모든 레벨이 완전히 채워짐 마지막 레벨의 노드는 왼쪽부터 채워짐
• Balanced Binary Tree : 모든 리프 노드까지의 거리가 거의 동일함

Binary Search Tree :  좌측 하위의 모든 노드가 부모 노드보다 작고, 우측 하위 모든 노드가 부모 노드보다 큽니다.

• Balanced BST
  • AVL Tree : 이진 검색트리를 기반으로 하며, 균형이 유지되도록 설계
  • Red-Balck Tree : 이진 검색트리를 기반으로 하며, 노드에 색상을 부여해 균형을 유지

다진 검색 트리 : B-Tree 와 B+ Tree는 DB와 파일 시스템에서 주로 사용. 노드가 여러개의 자식을 가질 수 있어 디스크 접근을 최소화

Tree 사용 사례

• 트리는 조부모 > 부모 > 자식 관계와 같이 계층적 구조를 갖는 자료 구조
• 계층적 구조가 필요한 상황
  • HTML, XML등 문서 개체 모델 (DOM)
  • 추상구문트리 (AST)
• 검색 트리를 통해 효유적인 검색 알고리즘 구현이 가능함.

Tree를 볼때는 Recursive 안경을 착용하자.

트리를 제대로 구현하고 활용하려면 "재귀"에 대한 이해가 반드시 필요

트리는 재귀적인 구조를 가짐. 트리의 각 노드는 하나의 sub tree를 루트로 하는 트리로 볼수 있음.

이런 방식으로 트리는 자기 자신을 재귀적으로 정의할 수 있으며, 이 특성은 트리를 탐색하거나 조작할 때 용이함.

Binary Search Tree, BST - 검색에 특화된 이진 트리

이진트리란?

•  이진 트리를 구성하는 노드의 자식이 두개인 트리를 의미
• 자식 노드가 없는 경우, 자식을 하나 가진 경우, 자식을 둘 가진 경우
• 자식이 최대 둘이기 때문에 왼쪽자식과 오른쪽 자식으로 구분
• 데이터 셋을 이분할 때, 무엇을 기준으로 이분 할지에 따라서 특화된 이진트리를 만들수 있음 그에 따라서 보다 효율적인 알고리즘을 만들 수 있는데 그 중에 하나가 이진 탐색 트리.

이진 검색 트리 알고리즘 (검색/삽입/삭제)

public class Node{
  pulbic int data;
  public Node left;
  public Node right;
}

public class BinarySearchTree{
  private Node root;
  
  public Node Search();
  public Node insert();
  public Node delete();
 
 }

탐색

Tree를 순회하면서 탐색하는 방법은 여러가지가 있습니다.

• BFS : 낮은 Level에서 시작해 왼쪽 -> 오른쪽 탐색
• DFS: 리프 노드에 이를때 까지 아래로 탐색
  • 전위 순회
  • 중위 순회
  • 후위 순회
• BFS와 DFS는 Tree나 Graph의 모든 노드를 한 번씩 방문애햐 하는 경우 적합 (ex:Tree복사, Tree 값 모두 출력)
• 이진 탐색 트리에서 특정 값을 찾을 때는 주로 이진 탐색 알고리즘 사용
  • 1. 탐색을 시작할때
  • 2.
  • 3.

이진트리란

이진트리와 이진 탐색

Binary Search Tree

시간 복잡도

BST 구현

4 Balancecd BST - BST 문제점 보완

5. AVL Tree

AVL 트리는 BST를 개선한 균형 이진 검색 트리입니다.

[...]

AVL Tree란

AVL 트리는 어떻게 균형을 유지할까?

회전 알고리즘

AVL Tree 구현의 핵심

6. Tree traversal - BFS & DFS

DFS

DFS 구현

BFS

BFS 구현

2

1

Hash Table 설명

검색 삽입삭제 ..