반응형
이진 탐색 트리 (Binary Search Tree)란?
자식 노드가 최대 두 개인 노드들로 구성된 트리이다. 이 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있다. 이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉜다
- 정 이진 트리(Full binary tree) : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다.
- 완전 이진 트리(Complete binary tree) : 정 이진 트리이면서 완전 이진 트리인 경우이다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리이다.
- 포화 이진 트리(Perfect binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.
이진 탐색 트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다.
이진 트리 순회
전위 순회 (preorder traverse)
가장 먼저 방문할 노드는 루트이다. 루트에서 시작해 왼쪽의 노드들을 순차적으로 탐색한 뒤, 오른쪽 노드를 탐색한다.
전위 순회 결과 : A - B - D - E - C - F - G
중위 순회 (inorder traverse)
왼쪽의 노드들을 순차적으로 탐색한 뒤, 루트 노드를 방문한다. 그리고 오른쪽 노드를 탐색 한다.
중위 순회 결과 : D - B - E - A - F - C - G
후위 순회 (postorder traverse)
왼쪽 노드들을 순차적으로 탐색 한 뒤, 오른쪽 노드를 탐색한다. 그리고 루트 노드를 방문한다.
후위 순회 결괴 : D - E - B - F - G - C - A
이진트리 효율성
데이터의 탐색 속도를 올리기 위해 사용하는 구조이다.
데이터를 검색할 때 전체 데이터를 검색하지 않고, 해당 데이터 집합에서의 중간값을 찾아 크기를 비교하는 방식으로 데이터를 검색한다.
중간값을 구해서 중간값보다 크거나 작은 지를 판단해서 왼쪽, 오른쪽 노드 지정
노드의 개수가 N개이면 시간 복잡도는 O(logN)이다.
이진트리 구현
노드 클래스 만들기
// 트리를 구성하는 노드 클래스입니다.
public static class Node {
private int data;
private Node left;
private Node right;
/* 생성자 */
public Node(int data) {
this.setData(data);
setLeft(null);
setRight(null);
}
public int getData() {
return data;
}
public Node getLeft() {
return left;
}
public Node getRight() {
return right;
}
public void setData(int data) {
this.data = data;
}
public void setLeft(Node left) {
this.left = left;
}
public void setRight(Node right) {
this.right = right;
}
}
삽입 연산
삽입 연산에서 가장 먼저 하는 일은 root노드가 존재하는지 확인한다.
root 노드가 존재하지 않으면 해당 트리의 노드가 없다는 뜻이므로 새로운 newNode를 root노드로 만들어주고 return 한다.
public void insert(int data) {
Node newNode = new Node(data); // 왼쪽, 오른쪽 자식 노드가 null 이며 data 의 값이 저장된 새 노드 생성
if (root == null) {// 루트 노드가 없을때, 즉 트리가 비어있는 상태일 때,
root = newNode;
return;
}
if(root.data == data) return; //중복일때 정지
Node currentNode = root;
Node parentNode = null;
while (true) {
parentNode = currentNode;
if (data < currentNode.getData()) { // 해당 노드보다 작을 경우
currentNode = currentNode.getLeft();
if (currentNode == null) { // 더 이상 자식 노드가 없을 떄, 즉 삽입 할 수 있는 때
parentNode.setLeft(newNode);
return;
}else if(currentNode.data == newNode.data) return;
} else { // 해당 노드보다 클 경우
currentNode = currentNode.getRight();
if (currentNode == null) { // 더 이상 자식 노드가 없을 떄, 즉 삽입 할 수 있는 때
parentNode.setRight(newNode);
return;
}else if(currentNode.data == newNode.data) return;
}
}
}
삭제 연산
케이스를 나누어서 연산을 한다.
- 자식 노드가 없는 경우
- 하나의 자식 노드를 갖는 경우
- 두 개의 자식 노드를 갖는 경우
public boolean delete(int data){
Node parentNode = root;
Node currentNode = root;
boolean isLeftChild = false;
while(currentNode.getData() != data) {
parentNode = currentNode;
if(currentNode.getData() > data) {
isLeftChild = true;
currentNode = currentNode.getLeft();
}else {
isLeftChild = false;
currentNode = currentNode.getRight();
}
if(currentNode == null){
return false;
}
}
// 1. 자식 노드가 없는 경우
if(currentNode.getLeft() == null && currentNode.getRight() == null) {
if(currentNode == root) {
root = null; // 해당 노드가 root node일 경우
}
if(isLeftChild) {
parentNode.setLeft(null); // 삭제할 노드가 부모 노드의 왼쪽 자식일 경우
}
else {
parentNode.setRight(null); // 삭제할 노드가 부모 노드의 오른쪽 자식일 경우
}
}
// 2-1. 자식 노드가 하나인 경우(오른쪽 자식이 없을 때)
else if(currentNode.getRight() == null){
parentNode.setLeft(currentNode.getLeft());
}
// 2-2. 자식 노드가 하나인 경우(왼쪽 자식이 없을 떄)
else if(currentNode.getLeft() == null) {
parentNode.setRight(currentNode.getRight());
}
// 3. 자식이 둘인 경우
else {
Node minimum = getMinumun(currentNode);
if(currentNode == root) {
root = minimum;
}else if (isLeftChild){
parentNode.setLeft(minimum);
}else {
parentNode.setLeft(currentNode.getLeft());
}
minimum.setLeft(currentNode.getLeft());
}
return false;
}
탐색 연산
이진 탐색의 특성 왼쪽 자식 노드의 값은 현재 노드보다 항상 작아야 하고 오른쪽 자식 노드의 값은 현재 노드의 값 보다 항상 커야 한다라는 특징을 만족해야 한다.
public boolean contains(int data) {
Node currentNode = root;
while (currentNode != null) {
// 찾는 value값이 노드의 value와 일치한다면, true를 리턴합니다.
if (currentNode.data == data) {
return true;
}
if (currentNode.data > data) {
// 찾는 value값이 노드의 value 보다 작다면, 현재 노드를 left로 변경후 다시 반복합니다.
currentNode = currentNode.left;
}else {
// 찾는 value값이 노드의 value 보다 크다면, 현재 노드를 right로 변경후 다시 반복합니다.
currentNode = currentNode.right;
}
}
return false;
}
전체 코드
public class Main {
// 트리를 구성하는 노드 클래스입니다.
public static class Node {
private int data;
private Node left;
private Node right;
/* 생성자 */
public Node(int data) {
this.setData(data);
setLeft(null);
setRight(null);
}
public int getData() {
return data;
}
public Node getLeft() {
return left;
}
public Node getRight() {
return right;
}
public void setData(int data) {
this.data = data;
}
public void setLeft(Node left) {
this.left = left;
}
public void setRight(Node right) {
this.right = right;
}
}
//이진 탐색 트리의 클래스입니다.
public static class binarySearchTree {
public Node root;
public binarySearchTree(){
root = null;
}
// 삽입 연산
public void insert(int data) {
Node newNode = new Node(data); // 왼쪽, 오른쪽 자식 노드가 null 이며 data 의 값이 저장된 새 노드 생성
if (root == null) {// 루트 노드가 없을때, 즉 트리가 비어있는 상태일 때,
root = newNode;
return;
}
if(root.data == data) return; //중복일때 정지
Node currentNode = root;
Node parentNode = null;
while (true) {
parentNode = currentNode;
if (data < currentNode.getData()) { // 해당 노드보다 작을 경우
currentNode = currentNode.getLeft();
if (currentNode == null) { // 더 이상 자식 노드가 없을 떄, 즉 삽입 할 수 있는 때
parentNode.setLeft(newNode);
return;
}else if(currentNode.data == newNode.data) return;
} else { // 해당 노드보다 클 경우
currentNode = currentNode.getRight();
if (currentNode == null) { // 더 이상 자식 노드가 없을 떄, 즉 삽입 할 수 있는 때
parentNode.setRight(newNode);
return;
}else if(currentNode.data == newNode.data) return;
}
}
}
// 탐색 연산
public boolean contains(int data) {
Node currentNode = root;
while (currentNode != null) {
// 찾는 value값이 노드의 value와 일치한다면, true를 리턴합니다.
if (currentNode.data == data) {
return true;
}
if (currentNode.data > data) {
// 찾는 value값이 노드의 value 보다 작다면, 현재 노드를 left로 변경후 다시 반복합니다.
currentNode = currentNode.left;
}else {
// 찾는 value값이 노드의 value 보다 크다면, 현재 노드를 right로 변경후 다시 반복합니다.
currentNode = currentNode.right;
}
}
return false;
}
// 삭제 연산
public boolean delete(int data){
Node parentNode = root;
Node currentNode = root;
boolean isLeftChild = false;
while(currentNode.getData() != data) {
parentNode = currentNode;
if(currentNode.getData() > data) {
isLeftChild = true;
currentNode = currentNode.getLeft();
}else {
isLeftChild = false;
currentNode = currentNode.getRight();
}
if(currentNode == null){
return false;
}
}
// 1. 자식 노드가 없는 경우
if(currentNode.getLeft() == null && currentNode.getRight() == null) {
if(currentNode == root) {
root = null; // 해당 노드가 root node일 경우
}
if(isLeftChild) {
parentNode.setLeft(null); // 삭제할 노드가 부모 노드의 왼쪽 자식일 경우
}
else {
parentNode.setRight(null); // 삭제할 노드가 부모 노드의 오른쪽 자식일 경우
}
}
// 2-1. 자식 노드가 하나인 경우(오른쪽 자식이 없을 때)
else if(currentNode.getRight() == null){
parentNode.setLeft(currentNode.getLeft());
}
// 2-2. 자식 노드가 하나인 경우(왼쪽 자식이 없을 떄)
else if(currentNode.getLeft() == null) {
parentNode.setRight(currentNode.getRight());
}
// 3. 자식이 둘인 경우
else {
Node minimum = getMinumun(currentNode);
if(currentNode == root) {
root = minimum;
}else if (isLeftChild){
parentNode.setLeft(minimum);
}else {
parentNode.setLeft(currentNode.getLeft());
}
minimum.setLeft(currentNode.getLeft());
}
return false;
}
Node getMinumun(Node deleteNode) {
Node minimum = null;
Node minimumParent = null;
Node currentNode = deleteNode.getRight();
while(currentNode != null) {
minimumParent = minimum;
minimum = minimumParent;
currentNode = currentNode.getLeft();
}
if(minimum != deleteNode.getRight()){
minimumParent.setLeft(minimum.getRight());
minimum.setRight(deleteNode.getRight());
}
return minimum;
}
//전위 순회
public ArrayList<Integer> preorderTree(Node root, int depth, ArrayList<Integer> list) {
if (root != null) {
list.add(root.getData());
preorderTree(root.getLeft(), depth + 1, list);
preorderTree(root.getRight(), depth + 1, list);
}
return list;
}
//중위 순회
public ArrayList<Integer> inorderTree(Node root, int depth, ArrayList<Integer> list) {
if (root != null) {
inorderTree(root.getLeft(), depth + 1, list);
list.add(root.getData());
inorderTree(root.getRight(), depth + 1, list);
}
return list;
}
//후위 순회
public ArrayList<Integer> postorderTree(Node root, int depth, ArrayList<Integer> list) {
if (root != null) {
postorderTree(root.getLeft(), depth + 1, list);
postorderTree(root.getRight(), depth + 1, list);
list.add(root.getData());
}
return list;
}
}
}반응형
'Language > Java' 카테고리의 다른 글
| [Java] 열거형 (enum) 정리 (1) | 2022.09.29 |
|---|---|
| [Java] 재귀 함수 (Recursion Function) 정리 (1) | 2022.09.29 |
| [Java] Map 정리 (4) | 2022.09.28 |
| [Java / 자료구조] 그래프 (Graph) 정리 (0) | 2022.09.26 |
| [Java] StringBuilder와 StringBuffer 정리 (0) | 2022.09.26 |