이진 탐색 트리
규칙
- 왼쪽 자식 노드의 키는 부모 노드의 키보다 작음
- 오른쪽 자식 노드의 키는 부모 노드의 키보다 큼
- 각각의 서브 트리도 이진 탐색 트리를 유지
- 중복된 키를 허용하지 않음
특징
- 이진 탐색 트리 규칙에 의해 데이터가 정렬됨
- 이진 트리에 비해 탐색이 빠름 (하지만, 균형 유지 필요)
균형 상태: O(logN)
불균형 상태: O(N)
탐색
- 찾고자 하는 데이터를 루트 노드부터 비교 시작
- 대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동
- 찾는 데이터가 없으면 null 반환
삽입
- 루트부터 비교 시작(중복 키 발견 시 노드 추가하지 않고 종료)
- 삽입할 키가 현재 노드보다 작으면 왼쪽으로 이동
- 삽입할 키가 현재 노드보다 크면 오른쪽으로 이동
- Leaf 노드에 도달 후 키 비교하여 작으면 왼쪽, 크면 오른쪽에 삽입
삭제
1) 삭제 대상 노드가 Leaf인 경우
- 삭제 대상 노드 삭제
- 부모 노드의 해당 자식 링크 null로 변경
2) 삭제 대상 노드에 자식 노드가 하나 있는 경우 - 자식 노드를 삭제 대상 노드의 부모 노드에 연결
- 삭제 대상 노드 삭제
3) 삭제 대상 노드에 자식 노드가 둘인 경우 - 삭제 대상 노드의 (왼쪽 서브 트리에서 가장 큰 노드 or 오른쪽 서브 트리에서 가장 작은 노드) 선택
- 선택한 노드를 삭제 대상 노드 위치로 올림
- 위로 올라가는 과정에서 다른 자식 노드들의 링크 연결 작업 진행
- 삭제 대상 노드 삭제
이진탐색트리 코드
//levelOrder 출력할 때 사용하기 위해 임포트
import java.util.LinkedList;
import java.util.Queue;
//사용할 Node 클래스 : 자신의 키값과 두개의 자식 노드를 가지고 있다
class Node {
int key; //키값
Node left; //왼쪽 자식 노드
Node right; //오른쪽 자식 노드
Node(int key, Node left, Node right) {
this.key = key;
this.left = left;
this.right = right;
}
}
//Node 객체로 이루어진 이진 탐색 트리 클래스
class BinarySearchTree {
Node head;
BinarySearchTree(int key){
// 생성자로 들어온 키값으로 트리의 헤드(루트) 노드를 만든다
this.head = new Node(key, null, null);
}
//원하는 키값을 이진 탐색 트리에 삽입하는 메소드
public void addNode(int key) {
if (this.head == null) { //헤드가 비어있으면 트리가 비어있다는 의미이므로, 삽입하려고한 노드를 헤드로 만들어준다
this.head = new Node(key, null, null);
} else { //헤드가 비어있지 않으면
Node cur = this.head; //cur에 head를 넣어준다
while (true) { //삽입할 위치를 찾을때까지 무한 루프
Node pre = cur; //pre에 cur을 넣어준다.
// pre는 cur을 쫒아다니면서 마지막에 cur의 위치가 null이 되었을때 cur의 위치에 새 노드를 만들고 pre와 연결해준다
if (key < cur.key) { //삽입하려는 key 값이 cur보다 작으면 왼쪽으로
cur = cur.left;
if (cur == null) { //cur의 위치가 null이면 비어있는 곳이란 뜻이므로, 삽입할 키값을 가진 노드를 생성해서 삽입해준다
pre.left = new Node(key, null, null);
break; //무한루프 탈출
}
} else { //삽입하려는 key 값이 cur보다 크면 오른쪽으로
cur = cur.right;
if (cur == null) { //cur의 위치가 null이면 비어있는 곳이란 뜻, 삽입할 키값을 가진 노드를 생성해서 삽입
pre.right = new Node(key, null, null);
break; //무한 루프 탈출
}
}
}
}
}
//원하는 키값을 이진 탐색 트리에서 삭제하는 메소드
public void removeNode(int key) {
Node parent = null;
Node successor = null;
Node predecessor = null;
Node child = null;
Node cur = this.head;
//cur을 헤드부터 시작해서 삭제하려는 키 값의 위치를 찾는 과정. 찾으면 cur이 삭제하려는 키 값의 위치가 됨
while(cur != null) { //cur이 null이 아닐동안 계속. 결국 끝까지 갔는데도 못만나면 null을 만나게 되고 루프 종료
if(key == cur.key) { //키값을 찾으면 break
break;
}
parent = cur; //cur을 계속 쫒아오는 parent를 만들어서 나중에 삭제 및 삭제 후 연결 작업때 사용
if(key < cur.key) { //key값이 현재 cur의 키값보다 작으면 왼쪽으로
cur = cur.left;
}
else { //key값이 현재 cur의 키값보다 크면 오른쪽으로
cur = cur.right;
}
}
if(cur == null) { //cur이 결국 트리의 끝까지 갔는데도 키값을 만나지 못해서 null로 끝남
System.out.println("key에 해당하는 노드가 없습니다");
return;
}
if(cur.left == null && cur.right == null) { //지우려는 키 값이 Leaf노드인 경우
if(parent == null) { //parent가 null이면 키 값이 헤드 노드인 상황
this.head = null; //헤드를 null로 바꿈(삭제)
}else{ //parent가 null이 아니면
if (parent.left == cur) { //parent의 left가 cur이면
parent.left = null; //left를 null로 바꿈(삭제)
} else { //parent의 right가 cur이면
parent.right = null; //right를 null로 바꿈(삭졔)
}
}
}else if((cur.left != null && cur.right == null) || (cur.left == null && cur.right != null)){ //지우려는 키 값이 자식 노드가 하나인 노드인 경우
if(cur.left != null) { //cur의 left가 null이 아니면
child = cur.left; //하나뿐인 자식 노드는 cur의 left
}else{ //cur의 right가 null이 아니면
child = cur.right; //하나뿐인 자식 노드는 cur의 right
}
if(parent == null){ //parent가 null이면
this.head = child; //삭제하려는 키 값의 cur 노드가 헤드였던 것이므로, 삭제되고 하나뿐인 자식 노드가 헤드가 된다
}else{ //parent가 null이 아니면
if(parent.left == cur){ //parent의 left가 삭제 대상 노드 cur이면
parent.left = child; //cur의 하나뿐인 자식노드 child를 parent의 left 자리에 대신 채워 넣음
}else { //parent의 right가 삭제 대상 노드 cur이면
parent.right = child; //cur의 하나뿐인 자식노드 child를 parent의 right 자리에 대신 채워 넣음
}
}
}else{ //지우려는 키 값이 자식이 두개인 경우. 왼쪽 서브 트리에서 가장 큰 노드를 찾아서 올리는 방법을 선택
predecessor = cur; //predecessor에 삭제 대상 노드를 할당
successor = cur.left; //successor은 삭제 대상 노드의 왼쪽 노드를 할당 -> 삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 노드를 찾을 예정이기 때문
while(successor.right != null) { //가장 큰 값을 찾는 과정. 오른쪽으로 계속 파고 들어가다가 null을 만나면 루프 종료
predecessor = successor; //predecessor가 successor을 계속 쫒아감. 부모 노드 처럼
successor = successor.right; //successor은 계속 큰 값을 찾아서 오른쪽으로 파고 들어감
}
//successor은 가장 큰 값을 위에서 할당받았고, 가장 큰 값익기 때문에 더 이상 오른쪽에는 노드가 없음
//만약 successor의 왼족에 노드가 있다면, successor은 이제 올라갈 것이기 때문에 successor의 현재 위치로 successor의 왼쪽노드를 옮긴다
//succer의 현재 위치가 predecessor의 오른쪽이다
predecessor.right = successor.left;
//왼쪽 서브트리에서 가장 큰 노드인 successor을 삭제 대상 노드인 cur의 위치로 삽입하기 위해
//successor의 left는 cur의 left를 할당. successor의 right는 cur의 right를 할당
//cur을 날려버리고 그 자리에 successor을 바꿔 낀 상태
successor.left = cur.left;
successor.right = cur.right;
if(parent == null) { //parent가 null이면, cur이 트리의 헤드였다는 뜻이므로, 이 트리의 헤드가 successor이 된다.
this.head = successor;
}else { //parent가 null이 아니면
if(parent.left == cur) { //parent의 left가 cur이었으면
parent.left = successor; //그 left 자리에 successor을 바꿔 낀다
}else{ //parent의 right가 cur이었으면
parent.right = successor; //그 right 자리에 successor을 바꿔 낀다
}
}
}
}
//이진 탐색 트리를 level order로 출력
public void levelOrder(Node node) {
Queue<Node> queue = new LinkedList<>();
queue.add(node); //출력을 시작할 Node를 맨처음 큐에 추가
while (!queue.isEmpty()) {
Node cur = queue.poll(); //큐에서 꺼내옴
System.out.print(cur.key + " ");
if (cur.left != null) { //cur의 left가 있으면 큐에 추가
queue.offer(cur.left);
}
if (cur.right != null) { //cur의 right가 있으면 큐에 추가
queue.offer(cur.right);
}
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
// Test code
// 노드 삽입
BinarySearchTree bst = new BinarySearchTree(20);
bst.addNode(10);
bst.addNode(30);
bst.addNode(1);
bst.addNode(15);
bst.addNode(25);
bst.addNode(13);
bst.addNode(35);
bst.addNode(27);
bst.addNode(40);
bst.levelOrder(bst.head);
// 노드 삭제
bst.removeNode(40);
bst.levelOrder(bst.head);
bst.removeNode(25);
bst.levelOrder(bst.head);
bst.removeNode(20);
bst.levelOrder(bst.head);
}
}이진탐색트리 코드(재귀 사용)
// BST 삽입, 삭제 코드를 재귀 형태로 구현
import java.util.LinkedList;
import java.util.Queue;
class Node{
int key;
Node left;
Node right;
Node(int key, Node left, Node right){
this.key = key;
this.left = left;
this.right = right;
}
}
class BinarySearchTree {
Node head;
BinarySearchTree(int key) {
this.head = new Node(key, null, null);
}
// 새로운 키값을 넣을 곳을 재귀로 찾아서 삽입하는 메소드
public Node addNodeRecursive(Node cur, int key) { //cur에는 트리의 헤드를 넣는다
// 1. 헤드가 비어있는 상황(트리가 없는 상태) - 시작하자마자 아래 조건문에 들어가서 삽입할 값이 헤드로 만들어져서 return 된다
// 2. 재귀로 진행하다가 null인 부분(빈 곳)을 만나면 새로운 노드를 만들어서 반환한다. cur.left나 cur.right로 새로운 노드가 삽입된다
if(cur == null){
return new Node(key,null,null);
}
if(key < cur.key){ //key값이 현재 노드의 키값보다 작으면 left로 재귀로 파고 들어간다
cur.left = addNodeRecursive(cur.left, key);
}else{ //key값이 현재 노드의 키값보다 크면 right로 재귀로 파고 들어간다
cur.right = addNodeRecursive(cur.right, key);
}
return cur; //새로운 노드가 추가된 트리가 반환된다
}
// 삭제할 키값을 받아서 재귀를 통해 찾아서 삭제하는 메소드
public Node removeNodeRecursive(Node cur, int key) { //cur에는 트리의 헤드를 넣는다.
// 1. 헤드가 비어있는 상황(트리가 없는 상태) = 시작하자마자 아래 조건문으로 들어가서 삽입할 값이 헤드로 만들어져서 return 된다
// 2. 재귀로 끝까지 탐색을 했는데 삭제하고자 한는 키값이 없어서 만나지 못하고 리프 노드 밑에 null을 만난 상태
if(cur == null){
return null; //삭제할 값이 없으므로 null 반환
}
if(key < cur.key){ //삭제할 키값이 현재 노드의 키값보다 작으면 left로 파고 들어간다
cur.left = removeNodeRecursive(cur.left, key);
}else if(key > cur.key){ //삭제할 키값이 현재 노드의 키값보다 크면 right로 파고 들어간다
cur.right = removeNodeRecursive(cur.right, key);
}else{ //삭제할 키값을 만난 상황 (key == cur.key)
if(cur.left == null){ //삭제할 노드의 left가 없으면
return cur.right; //right를 반환한다.
//즉 위의 if문들에서 호출된 cur.left나 cur.right로 현재 cur의 right를 넣어준다.
//그럼 cur이 없어지고 그 자리에 cur의 right가 들어간다
//만약 자식이 없는 상태라면 어차피 cur.right가 null로 반환될 것이기 때문에 cur이 없어지고 그 자리에 null이 들어간다
}else if(cur.right == null){ //삭제할 노드의 right가 없으면
return cur.left; //left를 반환한다. 위의 경우와 똑같다
}else{ //삭제할 노드가 두개의 자식 노드를 갖고 있으면
Node predecessor = cur; //predecessor는 부모 노드 역할로 현재 노드를 따라다님
Node successor = cur.left; //successor은 왼쪽 서브 트리에서 가장 큰 값을 찾으러 들어감
while(successor.right != null){ //가장 큰 값을 찾으러 오른쪽으로 계속 들어감
predecessor = successor; //predecessor는 부모 노드 역할
successor = successor.right; //계속 오른쪽으로 파고 들어감
}
//더 이상 right가 없는 노드를 찾아서(successor은 왼쪽 서브 트리에서 가장 큰 값을 가진 노드), null을 만나서 탈출
predecessor.right = successor.left; //successor의 값을 삭제 대상 노드(cur)의 자리로 올리기 위해, left가 있으면 successor의 자리로 보내고, 없으면 null이 됨
cur.key = successor.key; //삭제할 노드의 자리에 successor(왼쪽 서브 트리에서 가장 큰 값)을 넣음
}
}
return cur; //트리 반환
}
public void levelOrder(Node node) {
Queue<Node> queue = new LinkedList();
queue.add(node); //출력을 시작할 Node를 맨처음 큐에 추가
while (!queue.isEmpty()) {
Node cur = queue.poll(); //큐에서 꺼내옴
System.out.print(cur.key + " ");
if (cur.left != null) { //cur의 left가 있으면 큐에 추가
queue.offer(cur.left);
}
if (cur.right != null) { //cur의 right가 있으면 큐에 추가
queue.offer(cur.right);
}
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
// Test code
// 노드 삽입
BinarySearchTree bst = new BinarySearchTree(20);
bst.head = bst.addNodeRecursive(bst.head, 10);
bst.head = bst.addNodeRecursive(bst.head, 30);
bst.head = bst.addNodeRecursive(bst.head, 1);
bst.head = bst.addNodeRecursive(bst.head, 15);
bst.head = bst.addNodeRecursive(bst.head, 25);
bst.head = bst.addNodeRecursive(bst.head, 13);
bst.head = bst.addNodeRecursive(bst.head, 35);
bst.head = bst.addNodeRecursive(bst.head, 27);
bst.head = bst.addNodeRecursive(bst.head, 40);
bst.levelOrder(bst.head);
// 노드 삭제
bst.head = bst.removeNodeRecursive(bst.head,40);
bst.levelOrder(bst.head);
bst.head = bst.removeNodeRecursive(bst.head, 25);
bst.levelOrder(bst.head);
bst.head = bst.removeNodeRecursive(bst.head, 20);
bst.levelOrder(bst.head);
}
}
재귀를 사용하여 나타내는 것이 훨씬 보기쉽고 간단하다.
