이진 트리의 자바 구현
public class BinarySearchTree {
/**
* 루트 노드
*/
private static Node root;
static class Node {
int data;
Node left, right, parent;
public Node(int data) {
this.data = data;
}
}
public BinarySearchTree(int data) {
root = new Node(data);
}
/**
* 중위 순회
*
* @param node 시작 노드
*/
public void inorderTraversal(Node node) {
if (node != null) {
inorderTraversal(node.left);
System.out.print(node.data + ", ");
inorderTraversal(node.right);
}
}
/**
* 검색
*
* @param node 시작 노드
* @param data 검색할 값
* @return 노드 또는 null
*/
public Node search(Node node, int data) {
while (node != null && data != node.data) {
if (data < node.data) {
node = node.left;
} else {
node = node.right;
}
}
return node;
}
/**
* 최소값 찾기
*
* @param node 시작 노드
* @return 최소값 노드
*/
public Node findMinimum(Node node) {
while (node.left != null) {
node = node.left;
}
return node;
}
/**
* 최대값 찾기
*
* @param node 시작 노드
* @return 최대값 노드
*/
public Node findMaximum(Node node) {
while (node.right != null) {
node = node.right;
}
return node;
}
/**
* 전행 노드 ( predecessor )
*
* @param node 대상 노드
* @return 전행 노드
*/
public Node getPredecessor(Node node) {
// 왼쪽 서브트리가 존재하면 왼쪽 서브트리의 최대값 반환
if (node.left != null) {
return findMaximum(node.left);
}
Node parent = node.parent;
// 왼쪽 서브트리가 없으면 가장 낮은 조상 노드 반환
while (parent != null && node == parent.left) {
node = parent;
parent = parent.parent;
}
return parent;
}
/**
* 후속 노드 ( successor )
*
* @param node 대상 노드
* @return 후속 노드
*/
public Node getSuccessor(Node node) {
// 오른쪽 서브트리가 존재하면 오른쪽 서브트리의 최소값 반환
if (node.right != null) {
return findMinimum(node.right);
}
Node parent = node.parent;
// 오른쪽 서브트리가 없으면 가장 낮은 조상 노드 반환
while (parent != null && node == parent.right) {
node = parent;
parent = parent.parent;
}
return parent;
}
/**
* 삽입
*
* @param data 삽입할 값
*/
public void insert(int data) {
Node newNode = new Node(data);
Node parent = null;
Node current = root;
while (current != null) {
parent = current;
if (data < current.data) {
current = current.left;
} else {
current = current.right;
}
}
newNode.parent = parent;
if (parent == null) {
root = newNode;
} else if (data < parent.data) {
parent.left = newNode;
} else {
parent.right = newNode;
}
}
/**
* 삭제
*
* @param node 삭제할 노드
* @return 삭제된 노드
*/
public Node delete(Node node) {
Node target;
// 삭제할 노드가 자식이 하나 이하일 때
if (node.left == null || node.right == null) {
target = node;
} else {
// 두 자식이 있으면 후속 노드 사용
target = getSuccessor(node);
}
Node child;
if (target.left != null) {
child = target.left;
} else {
child = target.right;
}
if (child != null) {
child.parent = target.parent;
}
if (target.parent == null) {
root = child;
} else if (target == target.parent.left) {
target.parent.left = child;
} else {
target.parent.right = child;
}
if (target != node) {
node.data = target.data;
}
return target;
}
}
레드-블랙 트리의 자바 구현
레드-블랙 트리는 균형 이진 탐색 트리로, 삽입 및 삭제 연산 시 트리의 균형을 유지하여 O(log n)의 시간 복잡도를 보장합니다. 기본적인 연산(이중 순회, 검색, 최소값, 최대값, 전행, 후속)은 이진 트리와 유사합니다.
public class RedBlackTree {
/**
* 루트 노드
*/
private static Node root;
/**
* NIL 노드는 레드-블랙 트리의 리프 노드를 나타내는 특수 노드
* 검은색이며, 모든 leaf 노드 대신 사용됨
*/
private Node nil = new Node(true);
static class Node {
int data;
Node left, right, parent;
boolean isBlack; // true = 검은색, false = 빨간색
public Node(int data) {
this.data = data;
this.isBlack = false; // 새 노드는 기본적으로 빨간색
}
public Node(boolean isBlack) {
this.isBlack = isBlack;
}
public boolean equals(Node other) {
return this.data == other.data;
}
}
public RedBlackTree(int data) {
root = new Node(data);
root.isBlack = true; // 루트는 검은색
}
/**
* 중위 순회 (색상 포함 출력)
*
* @param node 시작 노드
*/
public void inorderTraversal(Node node) {
if (node != null && !node.equals(nil)) {
inorderTraversal(node.left);
String color = node.isBlack ? "B" : "R";
System.out.print(color + node.data + " ");
inorderTraversal(node.right);
}
}
/**
* 검색
*
* @param node 시작 노드
* @param data 검색할 값
* @return 노드 또는 null
*/
public Node search(Node node, int data) {
while (node != null && data != node.data) {
if (data < node.data) {
node = node.left;
} else {
node = node.right;
}
}
return node;
}
/**
* 최소값 찾기
*
* @param node 시작 노드
* @return 최소값 노드
*/
public Node findMinimum(Node node) {
while (node.left != null) {
node = node.left;
}
return node;
}
/**
* 최대값 찾기
*
* @param node 시작 노드
* @return 최대값 노드
*/
public Node findMaximum(Node node) {
while (node.right != null) {
node = node.right;
}
return node;
}
/**
* 전행 노드
*
* @param node 대상 노드
* @return 전행 노드
*/
public Node getPredecessor(Node node) {
if (node.left != null) {
return findMaximum(node.left);
}
Node parent = node.parent;
while (parent != null && node == parent.left) {
node = parent;
parent = parent.parent;
}
return parent;
}
/**
* 후속 노드
*
* @param node 대상 노드
* @return 후속 노드
*/
public Node getSuccessor(Node node) {
if (node.right != null) {
return findMinimum(node.right);
}
Node parent = node.parent;
while (parent != null && node == parent.right) {
node = parent;
parent = parent.parent;
}
return parent;
}
/**
* 왼쪽 회전
*
* @param node 회전 기준 노드 (오른쪽 자식 필수)
*/
public void rotateLeft(Node node) {
Node rightChild = node.right;
node.right = rightChild.left;
if (rightChild.left != null) {
rightChild.left.parent = node;
}
rightChild.parent = node.parent;
if (node.parent == null) {
root = rightChild;
} else if (node == node.parent.left) {
node.parent.left = rightChild;
} else {
node.parent.right = rightChild;
}
node.parent = rightChild;
rightChild.left = node;
}
/**
* 오른쪽 회전
*
* @param node 회전 기준 노드 (왼쪽 자식 필수)
*/
public void rotateRight(Node node) {
Node leftChild = node.left;
node.left = leftChild.right;
if (leftChild.right != null) {
leftChild.right.parent = node;
}
leftChild.parent = node.parent;
if (node.parent == null) {
root = leftChild;
} else if (node == node.parent.left) {
node.parent.left = leftChild;
} else {
node.parent.right = leftChild;
}
node.parent = leftChild;
leftChild.right = node;
}
/**
* 삽입
*
* @param data 삽입할 값
*/
public void insert(int data) {
Node newNode = new Node(data);
Node parent = null;
Node current = root;
while (current != null && current != nil) {
parent = current;
if (data < current.data) {
current = current.left;
} else {
current = current.right;
}
}
newNode.parent = parent;
if (parent == null) {
root = newNode;
} else if (data < parent.data) {
parent.left = newNode;
} else {
parent.right = newNode;
}
newNode.left = nil;
newNode.right = nil;
insertFixup(newNode);
}
/**
* 삽입 후 균형 복구
*
* @param node 삽입된 노드
*/
public void insertFixup(Node node) {
while (node.parent != null && !node.parent.isBlack && node.parent.parent != null) {
// 부모가 조부모의 왼쪽 자식인 경우
if (node.parent == node.parent.parent.left) {
Node uncle = node.parent.parent.right;
// 삼촌이 빨간색인 경우 - 색상 변경
if (uncle != nil && !uncle.isBlack) {
node.parent.isBlack = true;
uncle.isBlack = true;
node.parent.parent.isBlack = false;
node = node.parent.parent;
} else {
// 삼촌이 검은색이고 현재 노드가 오른쪽 자식인 경우
if (node == node.parent.right) {
node = node.parent;
rotateLeft(node);
}
// 삼촌이 검은색이고 현재 노드가 왼쪽 자식인 경우
node.parent.isBlack = true;
node.parent.parent.isBlack = false;
rotateRight(node.parent.parent);
}
} else {
// 부모가 조부모의 오른쪽 자식인 경우
Node uncle = node.parent.parent.left;
if (uncle != nil && !uncle.isBlack) {
node.parent.isBlack = true;
uncle.isBlack = true;
node.parent.parent.isBlack = false;
node = node.parent.parent;
} else {
if (node == node.parent.left) {
node = node.parent;
rotateRight(node);
}
node.parent.isBlack = true;
node.parent.parent.isBlack = false;
rotateLeft(node.parent.parent);
}
}
}
root.isBlack = true;
}
/**
* 삭제
*
* @param node 삭제할 노드
* @return 삭제된 노드
*/
public Node delete(Node node) {
Node target;
if (node.left == null || node.right == null) {
target = node;
} else {
target = getSuccessor(node);
}
Node child;
if (target.left != null && target.left != nil) {
child = target.left;
} else {
child = target.right;
}
if (child != null && child != nil) {
child.parent = target.parent;
} else {
child = nil;
child.parent = target.parent;
}
if (target.parent == null) {
root = child;
} else if (target == target.parent.left) {
target.parent.left = child;
} else {
target.parent.right = child;
}
if (target != node) {
node.data = target.data;
}
// 삭제된 노드가 검은색이면 균형 복구 필요
if (target.isBlack) {
deleteFixup(child);
}
return target;
}
/**
* 삭제 후 균형 복구
*
* @param node 재구성 시작 노드
*/
public void deleteFixup(Node node) {
while (node != root && (node == nil || node.isBlack)) {
if (node == node.parent.left) {
Node sibling = node.parent.right;
// 형제가 빨간색인 경우
if (!sibling.isBlack) {
sibling.isBlack = true;
node.parent.isBlack = false;
rotateLeft(node.parent);
sibling = node.parent.right;
}
// 형제의 두 자식이 모두 검은색
if ((sibling.left == nil || sibling.left.isBlack) &&
(sibling.right == nil || sibling.right.isBlack)) {
sibling.isBlack = false;
node = node.parent;
} else {
// 오른쪽 자식이 검은색
if (sibling.right == nil || sibling.right.isBlack) {
sibling.left.isBlack = true;
sibling.isBlack = false;
rotateRight(sibling);
sibling = node.parent.right;
}
// 오른쪽 자식이 빨간색
sibling.isBlack = node.parent.isBlack;
node.parent.isBlack = true;
sibling.right.isBlack = true;
rotateLeft(node.parent);
node = root;
}
} else {
Node sibling = node.parent.left;
if (!sibling.isBlack) {
sibling.isBlack = true;
node.parent.isBlack = false;
rotateRight(node.parent);
sibling = node.parent.left;
}
if ((sibling.left == nil || sibling.left.isBlack) &&
(sibling.right == nil || sibling.right.isBlack)) {
sibling.isBlack = false;
node = node.parent;
} else {
if (sibling.left == nil || sibling.left.isBlack) {
sibling.right.isBlack = true;
sibling.isBlack = false;
rotateLeft(sibling);
sibling = node.parent.left;
}
sibling.isBlack = node.parent.isBlack;
node.parent.isBlack = true;
sibling.left.isBlack = true;
rotateRight(node.parent);
node = root;
}
}
}
node.isBlack = true;
}
public static void main(String[] args) {
int[] values = { 21, 3, 6, 7, 12, 25, 17, 8, 15 };
RedBlackTree rbt = new RedBlackTree(21);
for (int i = 1; i < values.length; i++) {
rbt.insert(values[i]);
}
System.out.print("삽입 후: ");
rbt.inorderTraversal(root);
System.out.println();
rbt.delete(rbt.search(root, 21));
System.out.print("삭제 후: ");
rbt.inorderTraversal(root);
}
}