트리
부모 노드 밑에 여러 자식 노드가 연결되고, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태의 자료구조
단, 자식 노드의 자식이 부모로 연결되는 경우는 보통 트리로 인정되지 않음
rooted tree에서는 여러가지 용어를 정의
- 높이(height)는 루트의 높이를 0으로 하고, 자식의 높이를 원래 노드보다 1 큰 것으로 정의
- 말단 노드(leaf node)의 정의는 자식이 없는 노드
unrooted tree에서는 차수가 1인 노드로 말단 노드를 정의
Tree 관련 용어
- 노드(node): 트리를 구성하는 기본 원소
- 루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점
- 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드
- 자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드
- 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들
- 리프 노드(leaf node/leaf/terminal node): 자식이 없는 노드
- 경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서
- 길이(length): 출발 노드에서 도착 노드까지 거치는 노드의 갯수
- 깊이(depth): 루트 경로의 길이
- 레벨(level): 루트 노드(1) 로 부터 노드까지 연결된 엣지의 수의 합
- 높이(height): 가장 긴 루트 경로의 길이
- 차수(degree): 각 노드의 자식의 갯수
- 트리의 차수(degree of tree): 트리의 최대 차수
- 크기(size): 노드의 개수
- 너비(width): 가장 많은 노드를 갖고 있는 레벨의 크기
- Tree의 응용
- 이진트리(Binary Tree)
- 이진탐색트리(Binary Search Tree, BST)
- 스레드 이진 트리
- 힙(Heap)
- B-tree
- 포레스트(Forest)
- 트라이(Trie)
자료구조
- Tree 인터페이스 작성
- search 추상메서드와 insert 추상메서드 작성
- Comparable 인터페이스 타입의 원소를 저장할 수 있도록 제네릭 생성
- Node 클래스를 자식으로 갖는 또 다른 재귀 타입
public interface Tree<E extends Comparable> {
boolean search(E toFind);
void insert(E toInsert);
}Node 클래스 작성
- 데이터와 left, right Node 클래스를 재귀 타입으로 갖는 클래스
- constructor, Tree 인터페이스로부터 search, insert 메서드를 구현
public class Node<E extends Comparable> implements Tree<E> {
private E value;
private Tree<E> left;
private Tree<E> right;
public Node(E value, Tree<E> left, Tree<E> right) {
this.value = value;
this.left = left;
this.right = right;
}
public E getValue() { return value; }
public Tree<E> getLeft() { return left; }
public Tree<E> getRight() { return right; }
public void setLeft(Tree<E> left) { this.left = left; }
public void setRight(Tree<E> right) { this.right = right; }
@Override
public boolean search(E toFind) {
// right element 검색
if (toFind.equals(value)) return true;
/*
* toFind를 value와 비교하여 같으면 0, '>' 는 양수, '<'는 음수
* 음수일 경우 left Node를 검색
* 같거나 양수일 경우 right Node를 검색
*/
if (toFind.compareTo(value) < 0) { return left.search(toFind); }
// 위 조건문에서 양수일 경우 right Node를 검색
return right.search(toFind);
}
@Override
public void insert(E toInsert) {
/*
* toInsert 값을 value값과 비교하여 같으면 0, '>' 는 양수, '<'는 음수
* 음수일 경우 left Node에 삽입
* 같거나 양수일 경우 right Node에 삽입
*/
if (toInsert.compareTo(value) < 0) { left.insert(toInsert);
} else { right.insert(toInsert); }
}
}- Leaf 클래스
public class Leaf<E extends Comparable> implements Tree<E> {
private final Node<E> parent;
public Leaf(Node<E> parent) {
this.parent = parent;
}
@Override
public boolean search(E toFind) {
return false;
}
@Override
public void insert(E toInsert) {
/*
* toInsert 값을 상위노드 값과 비교, 같으면 0, '>' 는 양수, '<'는 음수
* 상위노드의 left 노드에 새로 Node 삽입
*/
if (toInsert.compareTo(parent.getValue()) < 0)
parent.setLeft(new Node<>(toInsert, new Leaf<>(parent), new Leaf<>(parent)));
else
parent.setRight(new Node<>(toInsert, new Leaf<>(parent), new Leaf<>(parent)));
}
}이진트리 검색 알고리즘
단순 트리 구조
- search를 통해 값이 있는지 확인
- insert를 통해 상위노드와 비교하여 값이 작으면 left 노드에 삽입, 값이 같거나 클 경우 right 노드에 삽입
public class SimpleTree<E extends Comparable> {
private E value;
private SimpleTree<E> left;
private SimpleTree<E> right;
public SimpleTree(E value, SimpleTree<E> left, SimpleTree<E> right) {
this.value = value;
this.left = left;
this.right = right;
}
public E getValue() { return value; }
public SimpleTree<E> getLeft() { return left; }
public SimpleTree<E> getRight() { return right; }
public boolean search(final E toFind) {
// 찾으려는 값이 Tree에 있는 것을 확인
if (toFind.equals(value)) return true;
/*
* toFind를 value와 비교하여 같으면 0, '>' 는 양수, '<'는 음수
* left 노드가 존재하고, 음수일 경우 left Node를 검색
* 같거나 양수일 경우 right Node를 검색
*/
if (toFind.compareTo(value) < 0 && left != null) return left.search(toFind);
return right != null && right.search(toFind);
}
public void insert(final E toInsert) {
// 입력할 값을 비교, 같으면 0, '>' 는 양수, '<'는 음수
if (toInsert.compareTo(value) < 0) {
// 입력 값이 작고, left Node가 null일 경우 새로 생성
if (left == null) left = new SimpleTree<>(toInsert, null, null);
// 입력 값이 작고, left Node가 null이 아닐 경우 삽입
else left.insert(toInsert);
} else {
// 입력 값이 같거나 크고, right Node 값이 null인 경우 새로 생성
if (right == null) right = new SimpleTree<>(toInsert, null, null);
// 입력 값이 같거나 크고, right Node 값이 null이 아닌 경우 새로 생성
else right.insert(toInsert);
}
}
}- 단순트리 검색 테스트
- 단순 트리 구조의 insert, search 테스트
public class SimpleTreeTest {
private SimpleTree<Integer> root;
@Before
public void createSampleTree() {
final SimpleTree<Integer> t1 = new SimpleTree<>(1, null, null);
final SimpleTree<Integer> t5 = new SimpleTree<>(5, null, null);
final SimpleTree<Integer> t3 = new SimpleTree<>(5, t1, t5);
final SimpleTree<Integer> t9 = new SimpleTree<>(9, null, null);
/* 7
* 5 9
* 1 5
*/
root = new SimpleTree<>(7, t3, t9);
}
@Test
public void search() {
assertTrue(root.search(7));
assertFalse(root.search(70));
}
@Test
public void insert() {
root.insert(10);
assertTrue(root.search(10));
/* 7
* 5 9
* 1 5 10
*/
assertEquals(Integer.valueOf(10), root.getRight().getRight().getValue());
}
@Test
public void createTree() {
final SimpleTree<Integer> root = new SimpleTree<>(7, null, null);
root.insert(3);
root.insert(9);
root.insert(10);
assertTrue(root.search(10));
/* 7
* 3 9
* 10
*/
assertEquals(Integer.valueOf(10), root.getRight().getRight().getValue());
}
@Test
public void linkedListTree() {
final SimpleTree<Integer> root = new SimpleTree<>(1, null, null);
root.insert(2);
root.insert(3);
root.insert(4);
root.insert(5);
/* 1
* 2
* 3
* 4
* 5
*/
assertEquals(Integer.valueOf(1), root.getValue());
assertEquals(Integer.valueOf(2), root.getRight().getValue());
assertEquals(Integer.valueOf(3), root.getRight().getRight().getValue());
assertEquals(Integer.valueOf(4), root.getRight().getRight().getRight().getValue());
assertEquals(Integer.valueOf(5), root.getRight().getRight().getRight().getRight().getValue());
}
}
- Complex 트리 검색
public class ComplexTreeTest {
@Test
public void insert() {
final Node<Integer> root = new Node<>(7, null, null);
root.setLeft(new Leaf<>(root));
root.setRight(new Leaf<>(root));
root.insert(3);
assertTrue(root.search(3));
assertFalse(root.search(13));
}
}
코드 참고 - 자바 프로그래밍 면접 이렇게 준비한다
'알고리즘&자료구조 > basic' 카테고리의 다른 글
| [알고리즘] 너비 우선 탐색(Breadth First Search, BFS) (0) | 2020.05.13 |
|---|---|
| [자료구조] 그래프(Graph) (0) | 2020.05.13 |
| [자료구조] 큐(Queue) (0) | 2020.05.12 |
| [자료구조] 스택(Stack) (0) | 2020.05.10 |
| [알고리즘] 계수 정렬(Counting Sort) (0) | 2020.05.10 |