Tree 자료구조

tree 자료구조

위와 같이 부모(root) 노드가 있고 그 아래로 자식 노드들을 가지는 형태의 자료구조를 tree 자료구조라고 한다.

트리자료구조의 종류

1. Binary Tree vs Ternary tree

binary tree

노드가 최대 2개의 자식 노드를 가지고 있는 tree자료구조를 binary tree라고한다.

ternary tree

노드가 위처럼 최대 3개의 자식 노드를 가지고 있는 경우 ternary tree.

2. Binary Search Tree(이진 검색 트리)

이진검색트리는 1번 경우 처럼 자식노드가 최대 2가지이다.
하지만 자식 노드의 가지고 있는 값이 부모(root)노드에 의해 나눠진다.
예를 들어 차이를 살펴 보자.

binary tree

binary tree는 자식노드가 부모 노드 아래로만 존재 할 뿐 자료의 값과는 아무 관련이 없다.

binary search tree

반면 binary search tree는
왼쪽 자식 노드는 부모노드 보다 작은값
오른쪽 자식 노드는 부모노드 보다 큰 값이 위치하게 된다.

3. Complete Binary Tree vs Full Binary Tree vs perfect binary tree

complete binary tree

complete binary tree는 자식노드가 있을 때 왼쪽부터 채워졌을 경우를 지칭한다. 아래와 같은 경우는 오른쪽부터 채워졌기 때문에 complete binary tree가 아니다.

complete binary tree가 아니다.

complete binary tree의 경우 중 자식노드가 존재 할 때 항상 2개를 가지고 있을 경우를 full binary tree라고 한다.

full binary tree

full binary tree

위의 두 가지 경우 다 complete binary tree이면서 full binary tree구조에 해당한다.

perfect binary tree

그 중에서도 완벽하게 피라미드의 형태를 하고 있는 위와 같은 경우를 perfect binary tree라고 한다.

tree 자료구조의 속성

부모노드(root)
자식노드
트리의 크기

tree 자료구조 메소드

addchild — 자식노드 추가
delete — 자식노드 삭제
contain — 특정 value가 존재하는 지 확인