[자료구조/JAVA] 트리 (1) : 이진 트리(Binary Tree) : 순회 및 연산
트리(Tree)
계층적인 구조를 표현하는 데 사용되는 비선형 자료 구조. 트리는 노드(node)들의 집합이며, 각 노드는 부모(parent)와 자식(children) 관계로 연결된다.
중요한 특징으로는 순환이 없다는 점이다. 어떤 경로를 따라 이동하더라도 한 노드를 두 번 이상 방문하지 않는다는 뜻이다. 따라서 트리는 계층적인 데이터를 효과적으로 표현할 수 있다.
트리는 데이터베이스에서는 인덱스 구조, 운영 체제의 파일 시스템을 구현하는 등 여러 분야에서 활용된다.
알고리즘에서는 이진 검색 트리(Binary Search Tree), 힙(Heap), AVL 트리, 레드-블랙 트리 등 다양한 종류의 트리로 응용된다.
트리의 구성 요소
- Root(루트) : 트리 최상위 노드
- Child(자식) : 노드 하위 연결 노드
- Degree(차수) : 자식 노드의 수
- Parent(부모) : 노드의 상위 연결 노드
- Leaf(리프) : 자식이 없는 노드 = 단말 노드 혹은 외부 노드
- Non-Terminal(비단말) / Internal Node(내부) : Leaf가 아닌 노드
- Subtree(서브트리) : 노드 자신과 후손 노드로 구성된 트리
- Level = Depth(레벨, 깊이) : 아래층으로 내려가며 레벨 증가, 루트노드는 레벨 1 혹은 0으로 시작한다. (1->수학적 관점, 0->프로그래밍적 관점)
- Height(높이) : 트리의 최대 레벨
- Key(키) : 탐색에 사용되는 노드에 저장된 정보
- Sibling(형제) : 동일한 부모의 노드
- Ancestor(조상) : 루트노드까지의 경로 상의 노드 집합
- Descendant(후손) : 말단까지의 노드 집합
이진 트리(Binary Tree)
정의 : 각 노드의 자식 수가 2 이하인 트리
이진트리는 루트 노드와 왼쪽 서브트리, 오른쪽 서브트리로 구성된다.
각 노드가 최대 두 개의 자식 노드를 가질 수 있기 때문에 데이터의 구조적인 관계를 효율적으로 반영할 수 있다.
효율적인 삽입과 탐색이 가능 : 이진트리의 서브트리를 다른 이진트리의 서브트리와 교환하는 것이 쉽기 때문이다. 각 서브트리는 다시 이진 트리가 될 수 있다.
https://en.wikipedia.org/wiki/Tree_%28graph_theory%29
특별한 형태의 이진트리
완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고, 마지막 레벨에서는 노드들이 왼쪽부터 빠짐없이 채워진 트리. 위의 그림은 완전 이진 트리이다.
포화 이진 트리(Full Binary Tree) : 모든 레벨에서 노드들이 가득 차 있으며 각 내부노드가 2개의 자식 노드를 가지는 이진 트리. 포화 이진트리는 완전 이진트리이다.
이진트리의 속성
1. 레벨 L의 최대 노드 수 : 2^(L-1)
오른쪽의 그림에서 L=4에서 최대 8개의 노드를 가질 수 있다.
2. 높이 H인 포화이진트리의 노드 수 : 2^H - 1
높이가 4인 경우, 포화 이진 트리일 경우 총 15개의 노드를 가진다. (8+4+2+1)
3. N개의 노드를 가진 완전이진트리의 높이 h : ceil(log2(N+1))
왼쪽의 완전이진트리는 12개의 노드를 가진다. 계산해보면 3< log2(13) <4 이므로 ceil 연산 시 4의 높이를 가진다.
배열로 구현하는 이진트리
배열로 이진 트리를 구현하는 방식이다. 아래의 규칙을 따른다.
- a[i]의 부모노드 : a[i/2], (단 i > 1)
- a[i]의 왼쪽 자식노드 : a[2i]
- a[i]의 오른쪽 자식노드 : a[2i + 1]
그렇지만 편향 이진트리와 같은 단적인 예시를 보면 알 수 있듯, 배열에 저장하는 경우 트리의 높이가 커질 수록 메모리의 낭비가 심해진다. 따라서 대부분 이진 트리는 연결 리스트를 통해 구현한다.
이진 트리의 구현 : 연결 리스트
class Node<T extends Comparable<T>> {
T item;
Node<T> left;
Node<T> right;
public Node(T item, Node<T> left, Node<T> right){
this.item = item;
this.left = left;
this.right = right;
}
public void setLeft(Node<T> left) {
this.left = left;
}
public void setRight(Node<T> right) {
this.right = right;
}
}
이진 트리의 노드를 정의하는 자바 클래스이다.
여기서 T는 임의의 Object를 Key로 설정하고, item(Key)를 비교하기 위해서 Comparable<T> 인터페이스를 구현한 일반 타입이다.
멤버 변수로는 Key(item)와, 이진 트리의 각 노드를 나타내는 왼쪽(left) 자식 노드, 오른쪽(right) 자식 노드를 가리키는 레퍼런스이다.
class BinaryTree<T extends Comparable<T>>{
Node<T> root;
public void setRoot(Node<T> n){
this.root = n;
}
public Node<T> getRoot(){
return this.root;
}
}
이진 트리를 구현한 클래스이다. 트리의 루트를 설정하고, 해당 루트로부터 다양한 연산을 수행하도록 작성할 예정이다.
static BinaryTree makeBinaryTree(Integer lastKey){
Node<Integer> n1 = new Node(100, null, null);
Node<Integer> n2 = new Node(200, null, null);
Node<Integer> n3 = new Node(300, null, null);
Node<Integer> n4 = new Node(400, null, null);
Node<Integer> n5 = new Node(500, null, null);
Node<Integer> n6 = new Node(600, null, null);
Node<Integer> n7 = new Node(700, null, null);
Node<Integer> n8 = new Node(lastKey, null, null);
//lastKey는 그냥 마지막 노드의 Key값을 함수로 받아 설정하기 위함. 800으로 설정하였다.
n1.setLeft(n2);
n1.setRight(n3);
n2.setLeft(n4);
n2.setRight(n5);
n3.setLeft(n6);
n3.setRight(n7);
n4.setLeft(n8);
BinaryTree<Integer> t = new BinaryTree<>();
t.setRoot(n1);
return t;
}
예제로 사용될 트리를 생성하는 코드이다. 해당 코드는 8개의 노드를 생성하고, set 함수를 이용하여 Parent-Child 계층 구조를 형성한다. 이후, BinaryTree의 루트 노드를 설정하고 트리를 반환하는 함수이다. 아래와 같은 형태의 이진 트리가 생성된다.
이진 트리의 연산 : 순회
트리의 노드를 순회할 때, 방문하는 순서를 결정하는 방법들이 있다.
1. 전위 순회 (Preorder)
루트 노드를 먼저 방문하고, 왼쪽 자식 트리를 전위 순회하고, 오른쪽 자식 트리를 전위 순회
NLR (Node, Left, Right) : 루트-왼쪽-오른쪽 순서
100 - 200 - 400 - 800 - 500 - 300 - 600 - 700
2. 중위 순회 (Inorder)
왼쪽 자식 트리를 중위 순회하고, 루트 노드를 방문하고, 오른쪽 자식 트리를 중위 순회
LNR (Left, Node, Right) : 왼쪽-루트-오른쪽 순서
표현식: LNR (Left, Node, Right)
800 - 400 - 200 - 500 - 100 - 600 - 300 - 700
3. 후위 순회 (Postorder)
왼쪽 자식 트리를 후위 순회하고, 오른쪽 자식 트리를 후위 순회하고, 루트 노드를 방문
LRN (Left, Right, Node) : 왼쪽-오른쪽-루트 순서
800 - 400 - 500 - 200 - 600 - 700 - 300 - 100
4. 레벨 순회 (Levelorder)
트리를 레벨별로 순회. 각 레벨의 노드를 왼쪽에서 오른쪽으로 방문
BFS (Breadth-First Search) 이다.
100 - 200 - 300 - 400 - 500 - 600 - 700 - 800
전위 순회 구현
public void preorder(){
this.preorder(this.root);
}
private void preorder(Node<T> n){
if(n != null){
System.out.print(n.item + " ");
preorder(n.left);
preorder(n.right);
}
}
preorder(): 외부에서 호출할 수 있는 메서드이며, 트리의 루트 노드부터 순회를 시작한다.
preorder(Node n): 해당 노드가 Root인 서브트리의 전위 순회를 시작하며, 재귀적 알고리즘 사용. 비어있는 서브 트리(현재 노드 n이 null)인 경우에는 순회 X
- 현재 노드 n에 저장된 항목을 출력
- n의 왼쪽 서브 트리를 재귀적으로 순회하기 위해 preorder(n.left)를 호출
- n의 오른쪽 서브 트리를 재귀적으로 순회하기 위해 preorder(n.right)를 호출
중위 순회와 후위 순회 구현
// 중위 순회
public void inorder(){
this.inorder(this.root);
}
private void inorder(Node<T> n){
if(n != null){
inorder(n.left);
System.out.print(n.item + " ");
inorder(n.right);
}
}
// 후위 순회
public void postorder(){
this.postorder(this.root);
}
private void postorder(Node<T> n){
if(n != null){
postorder(n.left);
postorder(n.right);
System.out.print(n.item + " ");
}
}
inorder(Node n) : 해당 노드가 Root인 서브트리의 중위 순회 시작
- 현재 노드 n에 저장된 항목을 출력
- n의 왼쪽 서브 트리를 재귀적으로 순회하기 위해 preorder(n.left)를 호출
- n의 오른쪽 서브 트리를 재귀적으로 순회하기 위해 preorder(n.right)를 호출
postorder(Node n) : 해당 노드가 Root인 서브트리의 후위 순회 시작
- n의 왼쪽 서브 트리를 재귀적으로 순회하기 위해 preorder(n.left)를 호출
- n의 오른쪽 서브 트리를 재귀적으로 순회하기 위해 preorder(n.right)를 호출
- 현재 노드 n에 저장된 항목을 출력
레벨 순회 구현
// 레벨 순회
public void levelorder(){
this.levelorder(this.root);
}
private void levelorder(Node<T> n){
Queue queue = new LinkedList<Node<T>>();
queue.add(n);
while(!queue.isEmpty()){
Node<T> current = (Node<T>) queue.poll();
System.out.print(current.item + " ");
if(current.left != null){
queue.add(current.left);
}
if(current.right != null){
queue.add(current.right);
}
}
}
leveloprder(Node n) : 해당 노드가 Root인 서브트리의 레벨 순회 시작
큐에 루트 노드 n을 추가 후 큐가 비어있지 않은 동안 아래의 내용을 반복한다.
- 큐에서 가장 먼저 들어왔던 노드를 순회한다(큐에서 dequeue)
- dequeue한 노드의 왼쪽 자식 노드가 존재한다면 왼쪽 자식 노드를 큐에 추가한다.
- 오른쪽 자식 노드도 존재한다면 큐에 추가한다.
- 다시 반복문을 수행하면서 큐가 비어있지 않다면 이를 반복한다.
이진 트리의 연산 : 노드의 수(N), 높이(Height), 동일 트리 판단
트리의 노드의 수와, Height 구하기
public int getHeight(){
return this.getHeight(this.root);
}
private int getHeight(Node<T> n){
if(n == null){
return 0;
}
else{
return 1 + Math.max(getHeight(n.left), getHeight(n.right));
}
}
public int getSize(){
return this.getSize(this.root);
}
private int getSize(Node<T> root){
if(root == null){
return 0;
}
else{
return 1 + getSize(root.left) + getSize(root.right);
}
}
기본적으로 전위 순회의 알고리즘을 사용한다.
노드의 수의 경우 [1 + 왼쪽 서브 트리의 노드의 수 + 오른쪽 서브 트리의 노드의 수] 이므로 이를 재귀적으로 계산하면 된다.
높이의 경우 [1 + max(왼쪽 서브 트리의 높이, 오른쪽 서브 트리의 높이)]이므로 마찬가지로 재귀적으로 계산할 수 있다.
트리 비교 및 동일 트리 판단
public boolean isEqual(BinaryTree<T> compare){
return this.isEqual(this.root, compare.root);
}
private boolean isEqual(Node<T> n, Node<T> m){
if(n == null || m == null){
return n == m; //둘 다 null일 경우 True, 아니면 False(XOR)
}
if (n.item.compareTo(m.item) != 0){
return false;
}
return isEqual(n.left, m.left) && isEqual(n.right, m.right);
}
매개변수로 들어온 트리와 동일한 트리인지를 판단하는 함수를 public 함수로 정의하였다.
내부적으로 두 개의 노드를 매개변수로 받아, 해당 노드들이 Root인 서브트리들이 일치하는지를 판단하는 함수를 작성하여 호출하였다.
해당 함수를 재귀적으로 호출하여 사용한다.
1. 우선 두 개의 현재 노드가 모두 null이거나, 모두 null이 아닌 경우에는 일치한다고 판단한다.
2. 현재 노드의 Key(item)을 비교하여 일치하지 않는 경우 false를 반환한다.
3. 왼쪽 자식 노드와, 오른쪽 자식 노드를 다시 Root 노드로 설정하고 서브트리에 대한 검사를 수행한다. 해당 함수를 재귀적으로 호출한다.
전체 코드
class Node<T extends Comparable<T>> {
T item;
Node<T> left;
Node<T> right;
public Node(T item, Node<T> left, Node<T> right){
this.item = item;
this.left = left;
this.right = right;
}
public void setLeft(Node<T> left) {
this.left = left;
}
public void setRight(Node<T> right) {
this.right = right;
}
}
class BinaryTree<T extends Comparable<T>>{
Node<T> root;
public void setRoot(Node<T> n){
this.root = n;
}
public Node<T> getRoot(){
return this.root;
}
// 전위 순회
public void preorder(){
this.preorder(this.root);
}
private void preorder(Node<T> n){
if(n != null){
System.out.print(n.item + " ");
preorder(n.left);
preorder(n.right);
}
}
// 중위 순회
public void inorder(){
this.inorder(this.root);
}
private void inorder(Node<T> n){
if(n != null){
inorder(n.left);
System.out.print(n.item + " ");
inorder(n.right);
}
}
// 후위 순회
public void postorder(){
this.postorder(this.root);
}
private void postorder(Node<T> n){
if(n != null){
postorder(n.left);
postorder(n.right);
System.out.print(n.item + " ");
}
}
// 레벨 순회
public void levelorder(){
this.levelorder(this.root);
}
private void levelorder(Node<T> n){
Queue queue = new LinkedList<Node<T>>();
queue.add(n);
while(!queue.isEmpty()){
Node<T> current = (Node<T>) queue.poll();
System.out.print(current.item + " ");
if(current.left != null){
queue.add(current.left);
}
if(current.right != null){
queue.add(current.right);
}
}
}
public int getHeight(){
return this.getHeight(this.root);
}
private int getHeight(Node<T> n){
if(n == null){
return 0;
}
else{
return 1 + Math.max(getHeight(n.left), getHeight(n.right));
}
}
public int getSize(){
return this.getSize(this.root);
}
private int getSize(Node<T> root){
if(root == null){
return 0;
}
else{
return 1 + getSize(root.left) + getSize(root.right);
}
}
public boolean isEqual(BinaryTree<T> compare){
return this.isEqual(this.root, compare.root);
}
private boolean isEqual(Node<T> n, Node<T> m){
if(n == null || m == null){
return n == m; //둘 다 null일 경우 True, 아니면 False(XOR)
}
if (n.item.compareTo(m.item) != 0){
return false;
}
return isEqual(n.left, m.left) && isEqual(n.right, m.right);
}
}
public class C01_BinaryTree {
static BinaryTree makeBinaryTree(Integer lastKey){
Node<Integer> n1 = new Node(100, null, null);
Node<Integer> n2 = new Node(200, null, null);
Node<Integer> n3 = new Node(300, null, null);
Node<Integer> n4 = new Node(400, null, null);
Node<Integer> n5 = new Node(500, null, null);
Node<Integer> n6 = new Node(600, null, null);
Node<Integer> n7 = new Node(700, null, null);
Node<Integer> n8 = new Node(lastKey, null, null);
n1.setLeft(n2);
n1.setRight(n3);
n2.setLeft(n4);
n2.setRight(n5);
n3.setLeft(n6);
n3.setRight(n7);
n4.setLeft(n8);
BinaryTree<Integer> t = new BinaryTree<>();
t.setRoot(n1);
return t;
}
public static void main(String[] args) {
BinaryTree t = makeBinaryTree(800);
System.out.print("Preorder : ");
t.preorder();
System.out.println();
System.out.print("Inorder : ");
t.inorder();
System.out.println();
System.out.print("Postorder : ");
t.postorder();
System.out.println();
System.out.print("Levelorder : ");
t.levelorder();
System.out.println();
System.out.println("Height : " + t.getHeight());
System.out.println("Size : " + t.getSize());
BinaryTree t2 = makeBinaryTree(800);
System.out.println("isEqual : " + t.isEqual(t2));
BinaryTree t3 = makeBinaryTree(700);
System.out.println("isEqual : " + t.isEqual(t3));
}
}
Preorder : 100 200 400 800 500 300 600 700
Inorder : 800 400 200 500 100 600 300 700
Postorder : 800 400 500 200 600 700 300 100
Levelorder : 100 200 300 400 500 600 700 800
Height : 4
Size : 8
isEqual : true
isEqual : false
이진 탐색 트리(Binary Search Tree)
지금까지 이진 트리를 구현하는 방법을 알아보았다. 그런데 의문이 드는 점이 있다.
트리는 분명 효율적인 저장을 위한 자료구조이고, 특정 Key값을 찾아내는 데에 유용해야 할 것이다. 그런데 지금까지 구현했던 내용은 수동으로 노드의 관계를 설정하고 전체를 순회하는 방법들에 대해서만 알아보았다.
이를 위해서 이진 트리의 특수한 형태인 이진 탐색 트리가 있으며, 정렬된 형태의 이진 트리이고 이는 탐색을 위한 트리로서 사용될 수 있다. 다음 규칙들이 추가되었다고 생각하면 된다.
구조 : 각 노드의 왼쪽 서브 트리에 있는 모든 값은 해당 노드의 값보다 작거나 같다. 오른쪽 서브 트리에 있는 모든 값은 해당 노드의 값보다 크거나 같다.
삽입 규칙: 새로운 값을 삽입할 때, 구조 규칙에 따라 트리를 탐색하며 적절한 위치를 찾는다.
특정 값 삭제 : 해당 노드를 삭제하고, 트리 구조 규칙에 맞추기 위해 재배치하는 로직을 거친다.
다음 포스팅에서는 이진 탐색 트리에 대해서 다루어 볼 예정이다.
'PS > 자료구조 & 알고리즘' 카테고리의 다른 글
| [자료구조/JAVA] 트리 (3) : AVL 균형 트리 (AVL Tree) (0) | 2024.03.25 |
|---|---|
| [자료구조/JAVA] 트리 (2) : 이진 탐색 트리(Binary Search Tree, BST) (0) | 2024.03.21 |
| [자료구조/JAVA] 연결 리스트(Linked List) (0) | 2024.03.13 |
| [자료구조/JAVA] 동적 배열(Dynamic Array) 구현 (1) | 2024.03.12 |
| [자료구조/JAVA] 스택과 큐(Stack, Queue) (0) | 2024.03.11 |
