트리(tree)
트리는 계층적인 자료를 나타내는 자료구조이다. 부모 노드가 여러 자식 노드들을 가질 수 있는 1대 다 구조임.
트리의 구성요소
- 부모 : 루트(root)노드 방향으로 직접 연결된 노드
- 자식 : 루트노드 반대 방향으로 직접 연결된 노드.
- 뿌리(root) : 부모 노드가 없는 최상위의 노드. 트리당 하나만 존재함
- 가지(branch) : 부모노드와 자식 노드가 모두 있는 노드.트리의 중간에 존재한다
- 길이 : 출발 노드에서 도착노드까지 거치는 수
- 깊이 : 루트 노드부터의 길이
- 차수 : 자식 노드의 개수
이진탐색트리(BinarySearchTree)
이진트리는 부모 노드가 자식 노드를 최대 2개까지 가질 수 있는 트리이다.
이진탐색트리는 이진속성, 탐색속성을 적용한 트리이다.
탐색
위 그림처럼 루트 노드부터 시작하여 탐색하는 값과 비교한다. 루트값이 작은 경우 왼쪽자식노드로 이동하고 큰 경우라면 오른쪽으로 이동한다.
삽입
삽입은 탐색과 비슷하다. 삽입할 값이 비교하는 값보다 작을 경우에는 왼쪽 자식노드로, 큰 경우 오른쪽 자식노드로 이동한다.
삭제
자식이 0개인 경우 부모노드의 자식노드를 null로 한다.
자식이 1개인 경우 삭제하는 노드의 부모와 지식을 연결 후 삭제한다.
자식이 2개인 경우 삭제하는 노드를 기준으로 오른쪽 자식 중 가작 작은값의 노드와 교체 후 삭제한다.
'C#은 처음이라' 카테고리의 다른 글
| Unity 상태 패턴 (1) | 2024.08.06 |
|---|---|
| C# 리스트(List) (0) | 2024.03.13 |
| C# 자료구조 (큐Queue) (0) | 2024.03.12 |
| C# 자료구조(스택) (0) | 2024.03.12 |
| C# 이벤트(Event)와 델리게이트(Delegate) (0) | 2024.03.11 |