728x90
들어가기에 앞서
해당 Post는 이진 트리에 대한 기초 지식을 요구합니다.
만약 이진트리를 모른다면 이 글을 읽고 난 이후 봐주시기 바랍니다.
이진 탐색 트리 값 삽입
이진트리 중 중복 값은 허용하지 않고, 왼쪽은 부모 노드보다 작은 값을 오른쪽 자식노드는 부모노드 보다 큰 조건을 충족하는 트리를 이진 탐색 트리라고 합니다.
위와 같이 데이터가 삽입되며, 왼쪽은 currnet보다 작은 값, 오른쪽은 큰 값을 배치하게 됩니다.
public class BinaryTree {
TreeNode<Integer> root;
public void add(Integer value) {
root = add(root, value);
}
private TreeNode<Integer> add(TreeNode<Integer> current, Integer value) {
if(current == null) {
return new TreeNode<>(value);
}
if(current.getValue() < value) {
current.setRight(add(current.getRight(), value));
} else {
current.setLeft(add(current.getLeft(), value));
}
return current;
}
}이진 탐색 트리의 삭제
이진 탐색 트리의 삭제는 어떤 상태를 가진 노드를 삭제하느냐로 3가지로 나눠볼 수 있습니다.
Leaf Node 삭제
가장 생각할 게 없는 단순한 삭제입니다.
자식 노드가 존재하지 않기 때문에 균형 이진트리가 아니라면 따로 큰 작업이 이뤄지지 않는 삭제입니다.
자식이 1개인 부모 Node 삭제
Leaf Node삭제보다 살짝 작업이 추가된 삭제라고 생각합니다.
자식이 1개일 경우 삭제할 노드의 부모 노드에 자식 노드의 Instance정보를 연결해 주고, 본인은 참조되지 않는 방법으로 간단하게 삭제처리할 수 있습니다.
자식이 2개인 부모 Node 삭제
자식이 2개인 경우 어떤 정책을 통해 부모 노드를 대체할 것인지를 고민해야 합니다.
- 중위 전임자(In-order Predecessor): 삭제할 노드의 왼쪽 서브트리에서 가장 큰 값을 가진 노드.
- 중위 후속자(In-order Successor): 삭제할 노드의 오른쪽 서브트리에서 가장 작은 값을 가진 노드.
위와 같이 정책을 정하여 삭제를 진행할 경우 데이터의 쏠림 현상으로 인해 시간복잡도가 차이 날 수 있는데,
평균적으로 O(log n)의 시간복잡도를 가지며, 최악의 경우 O(n)의 시간복잡도를 가지게 됩니다.
중위 전임자 정책을 사용하여 삭제하였을 경우
public class BinaryTree {
TreeNode<Integer> root;
private TreeNode<Integer> add(TreeNode<Integer> current, TreeNode<Integer> prevNode) {
if(current == null) {
return prevNode;
}
if(current.getValue() < prevNode.getValue()) {
current.setRight(add(current.getRight(), prevNode));
} else {
current.setLeft(add(current.getLeft(), prevNode));
}
return current;
}
public void remove(Integer value) {
root = remove(root, value);
}
private TreeNode<Integer> remove(TreeNode<Integer> current, Integer value) {
if(current == null) return null;
// 중위 전임자(In-order Predecessor)
if(Objects.equals(current.getValue(), value)) {
TreeNode<Integer> predecessor = predecessor(current.getLeft());
predecessor.setRight(current.getRight());
if(current.getLeft() != null)
add(predecessor, current.getLeft());
return predecessor;
}
current.setLeft(remove(current.getLeft(), value));
current.setRight(remove(current.getRight(), value));
return current;
}
// 중위 전임자(In-order Predecessor): 삭제할 노드의 왼쪽 서브트리에서 가장 큰 값을 가진 노드.
private TreeNode<Integer> predecessor(TreeNode<Integer> current) {
if(current.getRight() == null)
return current;
TreeNode<Integer> predecessor = predecessor(current.getRight());
if(Objects.equals(current.getRight().getValue(), predecessor.getValue()))
current.setRight(null);
return predecessor;
}
}
중위 후속자 정책을 사용하여 삭제하였을 경우
public class BinaryTree {
TreeNode<Integer> root;
private TreeNode<Integer> add(TreeNode<Integer> current, TreeNode<Integer> prevNode) {
if(current == null) {
return prevNode;
}
if(current.getValue() < prevNode.getValue()) {
current.setRight(add(current.getRight(), prevNode));
} else {
current.setLeft(add(current.getLeft(), prevNode));
}
return current;
}
public void remove(Integer value) {
root = remove(root, value);
}
private TreeNode<Integer> remove(TreeNode<Integer> current, Integer value) {
if(current == null) return null;
// 중위 후속자(In-order Successor)
if(Objects.equals(current.getValue(), value)) {
TreeNode<Integer> successor = successor(current.getRight());
successor.setLeft(current.getLeft());
if(current.getRight() != null)
add(successor, current.getRight());
return successor;
}
current.setLeft(remove(current.getLeft(), value));
current.setRight(remove(current.getRight(), value));
return current;
}
// 중위 후속자(In-order Successor): 삭제할 노드의 오른쪽 서브트리에서 가장 작은 값을 가진 노드.
private TreeNode<Integer> successor(TreeNode<Integer> current) {
if(current.getLeft() == null)
return current;
TreeNode<Integer> successor = successor(current.getLeft());
if(Objects.equals(current.getLeft().getValue(), successor.getValue()))
current.setLeft(null);
return successor;
}
}
최종 코드
public class BinaryTree {
TreeNode<Integer> root;
public BinaryTree() {
root = null;
}
public void add(Integer value) {
root = add(root, value);
}
private TreeNode<Integer> add(TreeNode<Integer> current, Integer value) {
if(current == null) {
return new TreeNode<>(value);
}
if(current.getValue() < value) {
current.setRight(add(current.getRight(), value));
} else {
current.setLeft(add(current.getLeft(), value));
}
return current;
}
private TreeNode<Integer> add(TreeNode<Integer> current, TreeNode<Integer> prevNode) {
if(current == null) {
return prevNode;
}
if(current.getValue() < prevNode.getValue()) {
current.setRight(add(current.getRight(), prevNode));
} else {
current.setLeft(add(current.getLeft(), prevNode));
}
return current;
}
public void remove(Integer value) {
root = remove(root, value);
}
private TreeNode<Integer> remove(TreeNode<Integer> current, Integer value) {
if(current == null) return null;
if(!Objects.equals(current.getValue(), value)) {
current.setLeft(remove(current.getLeft(), value));
current.setRight(remove(current.getRight(), value));
return current;
}
// Leaf일 때 삭제
if(current.getRight() == null && current.getLeft() == null)
return null;
if(current.getLeft() == null) return current.getRight();
if(current.getRight() == null) return current.getLeft();
// // 중위 전임자(In-order Predecessor)
// TreeNode<Integer> predecessor = predecessor(current.getLeft());
// predecessor.setRight(current.getRight());
// if(current.getLeft() != null)
// add(predecessor, current.getLeft());
// return predecessor;
// 중위 후속자(In-order Successor)
TreeNode<Integer> successor = successor(current.getRight());
successor.setLeft(current.getLeft());
if(current.getRight() != null)
add(successor, current.getRight());
return successor;
}
// 중위 전임자(In-order Predecessor): 삭제할 노드의 왼쪽 서브트리에서 가장 큰 값을 가진 노드.
private TreeNode<Integer> predecessor(TreeNode<Integer> current) {
if(current.getRight() == null)
return current;
TreeNode<Integer> predecessor = predecessor(current.getRight());
if(Objects.equals(current.getRight().getValue(), predecessor.getValue()))
current.setRight(null);
return predecessor;
}
// 중위 후속자(In-order Successor): 삭제할 노드의 오른쪽 서브트리에서 가장 작은 값을 가진 노드.
private TreeNode<Integer> successor(TreeNode<Integer> current) {
if(current.getLeft() == null)
return current;
TreeNode<Integer> successor = successor(current.getLeft());
if(Objects.equals(current.getLeft().getValue(), successor.getValue()))
current.setLeft(null);
return successor;
}
// 전위 순회 (Pre-order Traversal) 출력 메서드
public void traversePreOrder(TreeNode<Integer> node) {
if (node != null) {
System.out.print(" " + node.getValue());
traversePreOrder(node.getLeft());
traversePreOrder(node.getRight());
}
}
// 중위 순회 (In-order Traversal) 출력 메서드
public void traverseInOrder(TreeNode<Integer> node) {
if (node != null) {
traverseInOrder(node.getLeft());
System.out.print(" " + node.getValue());
traverseInOrder(node.getRight());
}
}
// 후위 순회 (Post-order Traversal) 출력 메서드
public void traversePostOrder(TreeNode node) {
if (node != null) {
traversePostOrder(node.getLeft());
traversePostOrder(node.getRight());
System.out.print(" " + node.getValue());
}
}
// 레벨 순회 (Level-order Traversal) 출력 메서드
public void traverseLevelOrder(TreeNode root) {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(" " + node.getValue());
if (node.getLeft() != null) queue.add(node.getLeft());
if (node.getRight() != null) queue.add(node.getRight());
}
}
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
bt.add(5);
bt.add(2);
bt.add(3);
bt.add(1);
bt.add(0);
bt.add(7);
bt.add(8);
bt.add(6);
bt.remove(5);
// 순회 결과 출력
System.out.print("Pre-order traversal:");
bt.traversePreOrder(bt.root);
System.out.println();
System.out.print("In-order traversal:");
bt.traverseInOrder(bt.root);
System.out.println();
System.out.print("Post-order traversal:");
bt.traversePostOrder(bt.root);
System.out.println();
System.out.print("Level-order traversal:");
bt.traverseLevelOrder(bt.root);
System.out.println();
}
}728x90
'알고리즘 문제풀이 > 자료구조' 카테고리의 다른 글
| [Tree] 이진 트리 순회 (1) | 2024.11.08 |
|---|---|
| [Tree] 이진 트리 ( Binary Tree ) (0) | 2024.11.07 |
| [자료구조] 스택(Stack) (0) | 2024.10.21 |
