자료구조 & 알고리즘/자료구조
Tree, Binary Tree, Binary Search Tree
maeng0830
2024. 1. 24. 19:47
Tree
트리(Tree)의 기본 개념
- 트리(Tree)는 그래프의 한 종류로 사이클이 없으며 계층적인 관계를 표현할 수 있는 비선형 자료구조이다.
- 특징에 따라 트리의 종류를 세분화할 수 있다. 대표적인 트리의 종류로는 이진트리(Binary Tree), 이진탐색트리(Binary Search Tree)가 있다.
트리 관련 용어
- 부모 노드: 자신과 연결된 노드 중 자신보다 높은 계층에 위치한 노드를 의미한다.
- 자식 노드: 자신과 연결된 노드 중 자신보다 낮은 계층에 위치한 노드를 의미한다.
- 루트 노드: 부모 노드가 없는 최상위 계층의 노드를 의미한다.
- 단말 노드: 자식 노드가 없는 최하위 계층의 노드를 의미한다.
- 내부 노드: 단말 노드가 아닌 노드를 의미한다.
- 형제 노드: 부모 노드가 같은 노드들을 의미한다.
- 깊이: 루트 노드로부터 특정 노드에 도달하기 위해 거쳐야하는 간선의 개수를 의미한다.
- 레벨: 특정 깊이에 있는 노드들의 집합을 의미한다.
- 차수: 특정 노드와 연결된 자식 노드의 개수를 의미한다.
이진 트리(Binary Tree)
- 이진 트리(Binary Tree)는 모든 노드의 최대 차수를 2로 제한한 트리를 의미한다. 즉 모든 노드가 자식 노드를 최대 2개만 가질 수 있는 트리를 의미한다.
- 노드들을 전위 순회(PreOrder), 중위 순회(InOrder), 후위 순회(PostOrder) 방법으로 순회할 수있다.
- 특정 조건에 대한 충족 여부에 따라 완전 이진 트리(Complete Binary Tree), 포화 이진 트리(Perfect Binary Tree), 이진 탐색 트리(Binary Search Tree)로 세분화 할 수 있다.
이진 트리 순회
- 전위 순회(PreOrder)
- 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드
- A -> B -> D -> H -> E -> I -> J -> C -> F -> G -> K
- 중위 순회(InOrder)
- 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드
- H -> D -> B -> I -> J -> B -> A -> F -> C -> G -> K
- 후위 순회(PostOrder)
- 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드
- H -> D -> I -> J -> E -> B -> F -> K -> G -> C -> A
완전 이진 트리(Complete Binary Tree), 포화 이진 트리(Perfect Binary Tree)
- 완전 이진 트리(Complete Binary Tree)는 아래의 특징을 충족하는 이진 트리이다.
- 최하위 계층을 제외한 모든 계층에 노드가 최대로 채워져있어야 한다.
- 최하위 계층은 왼쪽에서 오른쪽으로 노드가 채워져야한다.
- 포화 이진 트리(Perfect Binary Tree)는 아래의 특징을 충족하는 이진 트리이다.
- 트리의 최하위 계층까지 노드가 최대로 채워져있어야 한다.
이진 탐색 트리(Binary Search Tree)
- 이진 탐색 트리(Binary Search Tree)는 이진 트리의 데이터 구조에 제약을 줌으로써 더 빠른 탐색을 가능하게 한 이진 트리(Binary Tree)를 말한다.
이진 탐색 트리의 특징
- 이진 트리의 구조를 가진다.
- 왼쪽 자식 노드를 포함한 왼쪽 서브 트리는 부모 노드보다 작은 값을 가진다.
- 오른쪽 자식 노드를 포함한 오른쪽 서브 트리는 부모 노드보다 큰 값을 가진다.
- 중위 순회 시 오름 차순으로 노드를 탐색한다.
- 균형 상태일 때 이진 트리에 비해 탐색이 빠르다.
- 균형 상태는 모든 노드의 좌우 서브 트리의 높이가 1 이상 차이나지 않는 상태를 말한다.
- 일반적으로 중복된 값은 허용하지 않는다.
이진 탐색 트리의 삽입
- 루트 노드부터 시작하여 말단 노드까지 기존 노드의 값과 삽입될 노드의 값을 비교한다.
- 삽입될 노드의 값이 기존 노드의 값 보다 작으면, 왼쪽 자식 노드로 이동한다.
- 삽입될 노드의 값이 기존 노드의 값 보다 작으면, 오른쪽 자식 노드로 이동한다.
- 말단 노드의 값과 비교했을 때 삽입될 노드의 값이 작으면 왼쪽 자식 노드로, 크면 오른쪽 자식 노드로 삽입한다.
이진 탐색 트리의 삭제
- 삭제될 노드가 말단 노드인 경우
- 삭제될 노드와 부모 노드의 연결을 끊어준다.
- 삭제될 노드의 자식 노드가 1개인 경우
- 삭제될 노드의 자식 노드를 삭제될 노드의 부모 노드와 연결한다.
- 삭제될 노드의 자식 노드가 2개인 경우
- 삭제될 노드의 왼쪽 서브 트리에서 가장 큰 노드 OR 오른쪽 서브 트리에서 가장 작은 노드를 선택한다.
- 선택된 노드와 부모 노드의 연결을 끊는다.
- 선택된 노드의 자식 노드가 있다면, 자식 노드와 부모 노드를 연결한다.
- 선택된 노드와 삭제될 노드의 부모 노드를 연결한다.
- 삭제될 노드의 왼쪽 자식 노드, 오른쪽 자식 노드를 선택된 노드의 왼쪽 자식 노드, 오른쪽 자식 노드로 연결해 준다.
이진 탐색 트리의 탐색
- 루트 노드부터 시작하여 말단 노드까지 기존 노드의 값과 탐색할 값을 비교한다.
- 탐색할 값이 기존 노드의 값 보다 작으면, 왼쪽 자식 노드로 이동한다.
- 탐색할 값이 기존 노드의 값 보다 크면, 오른쪽 자식 노드로 이동한다.
- 탐색할 값을 발견하면 true를, 탐색할 값이 없다면 false를 반환하고 탐색을 종료한다.
이진 탐색 트리 구현
////////// Node //////////
public class Node<E extends Comparable<E>> {
E value;
Node<E> left;
Node<E> right;
public Node(E value) {
this.value = value;
}
}
////////// BinarySearchTree //////////
public class BinarySearchTree<E extends Comparable<E>> {
private Node<E> root; // 루트 노드
private int size; // 노드의 개수
public BinarySearchTree() {
this.root = null;
this.size = 0;
}
// 최소 데이터 탐색
public E min() {
return minNode(root);
}
private E minNode(Node<E> node) {
E minData = node.value;
// 루트 노드부터 -> 왼쪽 노드로 순회하면서, 가장 왼쪽 노드를 찾는다.
while (node.left != null) {
minData = node.value;
node = node.left;
}
return minData;
}
// 최대 데이터 탐색
public E max() {
return maxNode(root);
}
private E maxNode(Node<E> node) {
E maxData = node.value;
// 루트 노드부터 -> 오른쪽 노드로 순회하면서, 가장 오른쪽 노드를 찾는다.
while (node.right != null) {
maxData = node.value;
node = node.right;
}
return maxData;
}
// 전위 탐색
public List<E> preOrder() {
return preOrderTree(root, new ArrayList<>());
}
private List<E> preOrderTree(Node<E> node, ArrayList<E> visited) {
if (node == null) {
return visited;
}
visited.add(node.value);
preOrderTree(node.left, visited);
preOrderTree(node.right, visited);
return visited;
}
// 중위 탐색
public List<E> inOrder() {
return inOrderTree(root, new ArrayList<>());
}
private List<E> inOrderTree(Node<E> node, ArrayList<E> visited) {
if (node == null) {
return visited;
}
inOrderTree(node.left, visited);
visited.add(node.value);
inOrderTree(node.right, visited);
return visited;
}
// 후위 탐색
public List<E> postOrder() {
return postOrderTree(root, new ArrayList<>());
}
private List<E> postOrderTree(Node<E> node, List<E> visited) {
if (node == null) {
return visited;
}
postOrderTree(node.left, visited);
postOrderTree(node.right, visited);
visited.add(node.value);
return visited;
}
// 데이터 존재 여부 확인
public boolean contains(E value) {
return containsNode(root, value);
}
private boolean containsNode(Node<E> node, E value) {
if (node == null) {
return false;
}
/*
* a.compareTo(b)
* a < b : -1
* a == b : 0
* a > b : 1
*/
if (value.compareTo(node.value) == 0) {
return true;
} else if (value.compareTo(node.value) < 0) {
return containsNode(node.left, value);
} else {
return containsNode(node.right, value);
}
}
// 노드 삽입
public void insert(E value) {
if (root == null) {
root = new Node<>(value);
} else {
Node<E> cur = root;
while (true) {
Node<E> pre = cur;
if (value.compareTo(pre.value) == 0) {
System.out.println("중복된 데이터를 삽입할 수 없습니다.");
break;
} else if (value.compareTo(pre.value) < 0) {
cur = cur.left;
if (cur == null) {
pre.left = new Node<>(value);
break;
}
} else {
cur = cur.right;
if (cur == null) {
pre.right = new Node<>(value);
break;
}
}
}
}
size++;
}
public void removeNode(E value) {
Node<E> parent = null;
Node<E> successor = null; // 왼쪽 서브트리의 가장 큰 노드 OR 오른쪽 서브트리의 가장 작은 노드
Node<E> predecessor = null; // successor의 부모
Node<E> child = null; // successor의 자식 여부
Node<E> cur = root;
// 삭제 대상 찾기
while (cur != null) {
if (value == cur.value) {
break;
}
parent = cur;
if (value.compareTo(cur.value) < 0) {
cur = cur.left;
} else {
cur = cur.right;
}
}
// 삭제 대상이 없는 경우
if (cur == null) {
System.out.println("해당하는 데이터가 없습니다.");
return;
}
// 삭제 대상이 단말 노드인 경우
if (cur.left == null && cur.right == null) {
if (parent == null) {
root = null;
} else {
if (parent.left == cur) {
parent.left = null;
} else {
parent.right = null;
}
}
return;
}
// 삭제 대상의 자식이 1개인 경우
if ((cur.left != null && cur.right == null) || (cur.left == null && cur.right != null)) {
if (cur.left != null) {
child = cur.left;
} else {
child = cur.right;
}
if (parent == null) {
root = child;
} else {
if (parent.left == cur) {
parent.left = child;
} else {
parent.right = child;
}
}
return;
}
// 삭제 대상의 자식이 2개인 경우
predecessor = cur;
successor = cur.left;
while (successor.right != null) {
predecessor = successor;
successor = successor.right;
}
predecessor.right = successor.left;
successor.left = cur.left;
successor.right = cur.right;
if (parent == null) {
root = successor;
} else {
if (parent.left == cur) {
parent.left = successor;
} else {
parent.right = successor;
}
}
}
}
////////// 사용 예시 //////////
public class Main {
public static void main(String[] args) {
BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
binarySearchTree.insert(1);
binarySearchTree.insert(1);
binarySearchTree.insert(3);
binarySearchTree.insert(15);
binarySearchTree.insert(16);
binarySearchTree.insert(4);
binarySearchTree.insert(6);
binarySearchTree.insert(2);
binarySearchTree.insert(10);
List<Integer> preOrder = binarySearchTree.preOrder();
System.out.println(Arrays.toString(preOrder.toArray()));
// [1, 3, 2, 15, 4, 6, 10, 16]
List<Integer> inOrder = binarySearchTree.inOrder();
System.out.println(Arrays.toString(inOrder.toArray()));
// [1, 2, 3, 4, 6, 10, 15, 16]
List<Integer> postOrder = binarySearchTree.postOrder();
System.out.println(Arrays.toString(postOrder.toArray()));
// [2, 10, 6, 4, 16, 15, 3, 1]
binarySearchTree.removeNode(15);
binarySearchTree.removeNode(2);
List<Integer> preOrder2 = binarySearchTree.preOrder();
System.out.println(Arrays.toString(preOrder2.toArray()));
// [1, 3, 10, 4, 6, 16]
List<Integer> inOrder2 = binarySearchTree.inOrder();
System.out.println(Arrays.toString(inOrder2.toArray()));
// [1, 3, 4, 6, 10, 16]
List<Integer> postOrder3 = binarySearchTree.postOrder();
System.out.println(Arrays.toString(postOrder3.toArray()));
// [6, 4, 16, 10, 3, 1]
}
}
출처