🙋♂️ Tree란?
Tree란
Node들이 나무가지처럼 연결된 비선형 자료구조를 뜻한다.
Tree는Tree내 또 다른 하위Tree가 존재하며, 하위Tree내 또 다른 하위Tree가 존재하는
재귀적 자료구조이다.
상단 이미지와 같이 Tree는 이와 같은 구조로 표현할 수 있다.
👓 특징
Tree는 다음과 같은 특징을 가지고 있다.
- 하나의
Root노드와 0개 이상의 하위 트리로 구성된다. - 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조이다.
Tree내 또 다른Tree가 존재하는 재귀적 자료구조이다.- 단순
Loop가 아닌 방향이 없는 무방향 그래프 구조이다. - 노드 간 부모/자식 관계를 가지고 있는 계층형 자료구조이다. (부모는 하나만 가진다.)
- 노드가 n개인 트리는 항상 n-1개의
edge를 가진다.
🤷♂️ 종류
Tree의 종류는 여러가지가 있지만 흔히 볼 수 있는 구조의 Tree 3개만 알아보려 한다.
알아볼 Tree의 종류는 아래와 같다.
- 편향 트리(Skew Tree)
- 이진 트리(Binary Tree)
- 이진 탐색 트리(Binary Search Tree)
📶 편향 트리(Skew Tree)
Skew Tree는 모든 노드들이 자식 노드를 1개만 가진 Tree이다.
왼쪽방향으로 자식을 하나씩만 가진다면 Left Skew Tree, 오른쪽방향으로 자식을 하나씩만 가진다면 Right Skew Tree라고 하며, 그 외엔 Skew Tree이다.
🌲 이진 트리(Binary Tree)
Binary Tree는 각 노드가 최대 2개의 자식 노드를 가질 때 Binary Tree라고 한다.
Binary Tree의 자식 노드는 최대 2개의 자식 노드로 이루어지기 때문에 자식 노드가 1개일 수도 없을 수도 있다.
자식 노드는 왼쪽 or 오른쪽 자식 노드로 표현한다.
Binary Tree는 아래와 같이 노드의 상태에 따라 구분할 수 있다.
Full Binary TreePerfect Binary TreeComplete Binary Tree
정 이진 트리(Full Binary Tree)
모든 노드가 2개의 자식을 가지거나 자식이 없는 경우에 Full Binary Tree라고 한다.
쉽게 말해 자식 노드가 한개인 경우가 없어야 한다.
포화 이진 트리(Perfect Binary Tree)
이름과 어울리게 Perfect Binary Tree는 모든 노드가 2개의 자식 노드를 가지고 있고,
모든 leaf노드가 모두 같은 레벨이여야 한다.
말 그대로 모든 트리가 꽉 차 있는 경우를 말한다.
완전 이진 트리(Complete Binary Tree)
Complete Binary Tree는 두가지의 조건을 충족하면 Complete Binary Tree라고 한다.
조건은 아래와 같다.
- 마지막 레벨을 제외하고 모든 노드가 채워져 있어야 한다.
- 노드는 왼쪽에서 오른쪽 방향으로 채워져야한다.
🔍 이진 탐색 트리(Binary Search Tree)
Binary Search Tree는 이진 트리를 기반으로한 탐색을 위한 자료구조이다.
Binary Search Tree는 왼쪽 노드로는 자신보다 작은 노드를, 오른쪽 노드로는 자신보다 큰 노드를 가리킨다.
Binary Search Tree의 값(value)는 중복되지 않아야한다.
또한 서브 트리 또한 Binary Search Tree로 이루어져야한다.
Binary Search Tree는 이진 트리(Binary Tree)에 비하여 탬색 속도가 빠르다.
Binary Search Tree Class 구현
Binary Search Tree를 구현해보았다.
public class BinarySearchTree {
private root; // root 노드
class Node { // inner class로 Node class 선언
int value; // 값
Node left; // 왼쪽 노드 (작은)
Node right; // 오른쪽 노드 (큰)
// 생성자
Node(int value) {
this.value = value;
}
}
}public static void main(String[] args) {
BinarySearchTree myBST = new BinarySearchTree();
}이렇게 하면 root가 null인 BinarySearchTree를 생성할 수 있다.
하지만 값이 안들어가 있고 넣을 수 있는 방법조차 없기 때문에 삽입을 하는 insert메서드를 작성하였다.
Binary Search Tree에 Insert하기
public boolean insert(int value) {
Node newNode = new Node(value); // 새로운 노드를 생성
if(root == null) { // root가 null이라면 새로운 노드가 root가 되어야 한다.
root = newNode;
}
Node temp = root; // 임시 노드 포인터
while(true) { // 반복횟수를 모르기 때문에 true로 설정하고 while문 내부에서 return으로 빠져나올것이다.
if(newNode.value == temp.value) { // 중복 데이터 추가 X
return false;
}
if(newNode.value < temp.value) { // temp의 값보다 작으면 왼쪽
if(temp.left == null) { // temp의 왼쪽이 비었는지 확인
temp.left = newNode; // 삽입
return true;
}
temp = temp.left;
} else {
if(temp.right == null) { // temp의 값보다 큰경우이니 오른쪽
temp.right = newNode; // 삽입
return true;
}
temp = temp.right;
}
}
}insert에 성공하면 true 실패하면 false로 구분하기 위해 반환 타입을 boolean으로 하였다.
public static void main(String[] args) {
BinarySearchTree myBST = new BinarySearchTree();
myBST.insert(2);
myBST.insert(1);
myBST.insert(3);
System.out.println("Root: " + myBST.getRoot().value);
System.out.println("\nRoot->Left: " + myBST.getRoot().left.value);
System.out.println("\nRoot->Right: " + myBST.getRoot().right.value);
}위와 같이 호출해보면 제대로 값이 Tree내에 추가된걸 확인할 수 있다.
(getRoot 메서드는 단순히 root만 반환하는 메서드다.)
입력한 값이 Binary Search Tree에 존재하는지 확인
public boolean contains(int value) {
if(root == null) { // root가 비어있다면 트리에 아무것도 없는것(당연히 찾는 값도 없다.)
return false;
}
Node temp = root; // 임시 노드 포인터 생성
while(true) { // temp != null로 해서 null인 경우 빠져나와도 된다.
if(temp.value == value) { // 찾는 값이 있다면
return true;
}
if(temp.value > value) { // 찾는 값이 현재 temp값보다 작다면(왼쪽탐색)
if(temp.left == null) { // 왼쪽이 비었는지 확인. 만약 null이라면 없는거다
return false;
}
temp = temp.left;
} else { // 오른쪽 탐색
if(temp.right == null) { // 오른쪽이 비었는지 확인
retrun false; // 오른쪽이 비었으면 없는거다.
}
temp = temp.right;
}
}
}contains 메서드를 위와 같이 추가 후 호출해보면
public static void main(String[] args) {
BinarySearchTree myBST = new BinarySearchTree();
myBST.insert(2);
myBST.insert(1);
myBST.insert(3);
myBST.insert(47);
myBST.insert(21);
myBST.insert(76);
myBST.insert(18);
myBST.insert(27);
myBST.insert(52);
myBST.insert(82);
System.out.println("BST Contains 27:");
System.out.println(myBST.contains(27));
System.out.println("\nBST Contains 17:");
System.out.println(myBST.contains(17));
/*
EXPECTED OUTPUT:
----------------
BST Contains 27:
true
BST Contains 17:
false
*/
}위와 같이 원하는 값이 있는지 확인할 수 있다.
😄 마무리
Tree에 대하여 알아보게 되었는데 쉽게 이해할 수 있는 포인트가 있었다.
그것은 바로 LinkedList의 개념으로 포인터가 다음을 가리키는 개념이 있었는데, 그 개념이
BST나 다른Tree에도 동일하게 적용되는 개념임으로 쉽게 이해할 수 있었다.
이번엔 간단히 BST내 값을 추가하거나 값이 포함되있는지 확인하는 용도의 간단한 메서드를 작성했지만 BST에 대한 개념이 있다면 삭제, 수정등에 대한 코드도 잘 작성할 수 있을 것이라 생각한다.
또한 Heap에서도 BST에 대한 개념을 사용한다고 하는데 이 부분을 꼭 숙지하는 것이 중요하다고 생각이 들었다.
