트리 자료구조 구현하기
github.com/donghyeon0725/algorithm_java
donghyeon0725/algorithm_java
Contribute to donghyeon0725/algorithm_java development by creating an account on GitHub.
github.com
제 깃허브입니다.
설명링크
github.com/donghyeon0725/algorithm_java/blob/master/src/com/dataType/tree/README.md
donghyeon0725/algorithm_java
Contribute to donghyeon0725/algorithm_java development by creating an account on GitHub.
github.com
사진자료와 함께 설명하고 있기 때문에 위 링크로 들어가셔서 들을 읽고 오시는 것을 강력 추천합니다.
트리란
- 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 (Child 간의 연결이 없음)
- 실제로 사용되는 곳 : 트리의 한 종류로, 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨
알아두어야할 용어
| 용어 | 설명 |
| Node | 트리에서 데이터를 저장하는 기본 요소(데이터와 다른 연결된 노드에 대한 Branch 정보를 포함) |
| Root Node | 트리 맨 위에 있는 노드 |
| Level | 최상위 노드를 Level 0 으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 |
| Parent Node | 어떤 노드의 이전 레벨에 연결된 노드 |
| Chlid Node | 어떤 노드의 상위 레벨(더 낮은 가지)에 연결된 노드 |
| Leaf Node(Terminal Node) | Child Node가 하나도 없는 노드 |
| Sibling (Brother Node) | 동일한 Parent Node를 가진 노드 |
| Depth | 트리에서 Mode가 가지고 있는 최대 Level |
| Branch | 노드와 노드 사이의 연결 |
구현
- find => 노드를 따라 값의 대소를 비교해가며 찾기
- insert => 노드를 따라 값의 대소를 비교해가며 좌측 또는 우측 노드에 값을 삽입한다.
- delete
- Leaf Node 를 삭제하는 경우 => 그냥 삭제
- Child Node 가 하나인 경우 => 해당 노드를 삭제하고 parent 노드가 있던 자리에 Child 노드를 연결
- Child Node 가 두개인 경우 => 삭제할 노드 기준으로 좌측 노드의 자식 중 가장 큰 값이나, 우측 노드의 가장 작은 값을 삭제한 자리로 옮기면 된다. 다만, 그 값 또한 자식 노드가 있을 수 있는데, 그 노드는 옮겨질 노드의 부모 노드 아래쪽으로 옮겨주면 된다.
시간복잡도
- 트리의 높이(depth)를 h라고 표기한다면, O(h)
- n개의 노드를 가진다면 h = 2logn 에 가까우므로 시간복잡도는 O(logn)
- 한번 실행마다 50%의 탐색 수를 제거할 수 있음. => log 의 시간복잡도를 가지는 이유
- 다만, 데이터가 순차적으로 쌓이는 경우(연속적인 데이터가 쌓일 때) 링크드리스트와 동일한 O(n)의 성능을 보여줌(ArrayList는 검색의 경우 O(n))
구현
package com.dataType.tree;
public abstract class Tree<T> {
/**
* 노드에 왼쪽 오른쪽이 있음을 주의 깊게 본다.
* 연결 관계를 표시한 것이다.
* */
class Node<T> {
// 실제 데이터
private T data;
// 좌측 노드 (주소)
private Node left;
// 우측 노드 (주소)
private Node right;
public Node(T value) {
this.data = value;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
private Node root;
public Tree() {
this.root = null;
}
/**
* 비교 기준을 외부에서 구현 받는다.
* */
public abstract int compareTo(T t1, T t2);
/**
* 값을 비교해서 작으면 왼쪽으로 크면 우측으로 자식 노드를 찾아 나간다.
* 탐색시 있으면 true 반환
* */
public boolean find(T value) {
Node<T> newNode = new Node<>(value);
// 첫 노드를 기준으로
Node<T> parent = this.root;
while (parent != null) {
// 부모 노드보다 작은 경우 좌측 노드를 기준으로 다시 찾는다.
if (this.compareTo(parent.getData(), newNode.getData()) > 0) {
parent = parent.getLeft();
} else if (this.compareTo(parent.getData(), newNode.getData()) < 0) {
// 부모 노드보다 큰 경우
parent = parent.getRight();
} else {
// 비교값으로 객체를 찾고 equals 함수를 리턴
return true;
}
}
// Leaf Node 노드까지 탐색했는데도 없는 경우
return false;
}
/**
* 노드에서 데이터를 꺼내준다.
* */
public T get(T value) {
Node<T> result = getNode(value);
return result != null ? result.getData() : null;
}
/**
* 노드를 찾아서 있으면 리턴 없으면
* null 리턴
* */
private Node<T> getNode(T value) {
Node<T> newNode = new Node<>(value);
Node<T> parent = this.root;
// 부모 노드가 있으면 반복 => leafNode를 찾는 과정
while (parent != null) {
if (this.compareTo(parent.getData(), newNode.getData()) > 0) {
parent = parent.getLeft();
} else if (this.compareTo(parent.getData(), newNode.getData()) < 0) {
parent = parent.getRight();
} else {
return parent;
}
}
return null;
}
/**
* 부모 노드를 찾는다.
* 비교값을 비교해서 노드를 찾으면 그 이전에 찾았던 노드를 반환 하고 없으면 null
* */
private Node<T> getParentNode(T value) {
// 찾으려는 부모노드의 자식 노드
Node<T> newNode = new Node<>(value);
// 부모노드가 담길 공간
Node<T> parent = this.root;
// 부모노드를 잠시 저장해둘 공간
Node<T> target = this.root;
while (parent != null) {
if (this.compareTo(parent.getData(), newNode.getData()) > 0) {
// 부모 노드를 잠시 저장해둠
target = parent;
parent = parent.getLeft();
} else if (this.compareTo(parent.getData(), newNode.getData()) < 0) {
target = parent;
parent = parent.getRight();
} else {
return target;
}
}
return null;
}
/**
* 값을 비교해서 왼쪽 또는 오른쪽에 노드를 연결한다.
* */
public void insert(T value) {
// 받은 값을 통해서 노드를 생성
Node<T> newNode = new Node(value);
//노드가 비어있을 때
if (this.root == null) {
this.root = newNode;
return;
}
Node<T> parent = this.root;
while (parent != null) {
// 부모 노드보다 작은 경우
if (this.compareTo(parent.getData(), newNode.getData()) > 0) {
if (parent.getLeft() == null) {
parent.setLeft(newNode);
}
parent = parent.getLeft();
} else if (this.compareTo(parent.getData(), newNode.getData()) < 0) {
// 부모 노드보다 큰 경우
if (parent.getRight() == null) {
parent.setRight(newNode);
}
parent = parent.getRight();
} else {
// 같은 경우
return;
}
}
}
/**
* 노드를 삭제할 때 4가지 경우를 따져야 한다.
*
* 1. 없는 노드를 삭제하려는 경우
* => return
* 2. 자식 노드가 둘다 없는 경우
* => 대상 노드의 부모 노드로 부터 대상 노드와의 연결을 끊으면 됨
* 3. 하나의 자식 노드를 가진경우
* => 대상의 부모 노드로 부터 대상 노드가 있었던 위치(왼쪽, 오른쪽)에 대상 노드의 자식 노드만 연결해주면 됨
* 4. 자식이 둘다 있는 경우
* => 한쪽을 정해서 연결 관계를 재정의 해야함. 우측을 기준으로 하면, 대상 노드의 우측엔 대상 노드보다 큰 값이고 좌측은 착은 값이다.
* => 고로 우측에서 가장 작은 값을 찾으면 좌측의 모든 노드 값보다 큰 값이므로, 대상의 왼쪽 자식을 우측 자식중 제일 작은 노드의 왼쪽 자식으로 넣는다.
* => 그리고 대상의 우측에 있던 노드를 부모 노드와 연결한다. (원래 대상이 있던 위치에)
*
* 어려우면 설명 MarkDown 파일을 참고하길 바란다. (README.md 파일)
* */
public void delete(T value) {
Node<T> parent = getParentNode(value);
Node<T> target = getNode(value);
//노드를 찾지 못한 경우
if (parent == null) {
return;
}
boolean isRight = parent.getRight() == target;
// 둘다 없는 경우
if (target.getLeft() == null && target.getRight() == null) {
if (isRight) parent.setRight(null);
else parent.setLeft(null);
}
else if (target.getLeft() == null) {
Node<T> child = target.getRight();
if (isRight) parent.setRight(child);
else parent.setLeft(child);
}
else if (target.getRight() == null) {
Node<T> child = target.getLeft();
if (isRight) parent.setRight(child);
else parent.setLeft(child);
// 좌우 둘다 빈값이 아닌 경우
} else {
//우측에서 가장 작은 값을 찾음
Node<T> smallerNode = target.getRight();
while(smallerNode.getLeft() != null) {
smallerNode = smallerNode.getLeft();
}
smallerNode.setLeft(target.getLeft());
if (isRight) parent.setRight(target.getRight());
else parent.setLeft(target.getRight());
}
}
/**
* 디버깅 용도로 사용
* */
public void display(T value) {
Node<T> node = getNode(value);
T r = node.getRight() != null ? (T)node.getRight().getData() : null;
T l = node.getLeft() != null ? (T)node.getLeft().getData() : null;
System.out.println("좌측 자식 : " + (l != null ? l.toString() : null));
System.out.println("우측 자식 : " + (r != null ? r.toString() : null));
}
}
사용하기에 앞서
비교할 대상을 단순 숫자가 아닌, 객체(제네릭)로 만들었기 때문에 별도의 클래스가 필요합니다.
아래와 같은 클래스를 먼저 만들어줍니다.
Account
package com.dataType.speedTest;
public class Account {
private String name;
private int id;
public Account(String name, int id) {
this.name = name;
this.id = id;
}
public String getName() {
return name;
}
public Account setName(String name) {
this.name = name;
return this;
}
public int getId() {
return id;
}
public Account setId(int id) {
this.id = id;
return this;
}
@Override
public String toString() {
return "Account{" +
"name='" + name + '\'' +
", id=" + id +
'}';
}
}
사용
// Account 계정의 순서를 비교해서 정렬 기준을 만듬 => id값이 높을 수록
Tree<Account> tree = new Tree<Account>() {
@Override
public int compareTo(Account t1, Account t2) {
return t1.getId() - t2.getId();
}
/* @Override
public boolean equals(Account t1, Account t2) {
return this.compareTo(t1, t2) == 0;//t1.getId().equals(t2.getId()) && (t1.getOrder() == t2.getOrder());
}*/
};
Account account1 = new Account("one", 1);
Account account2 = new Account("two", 2);
Account account3 = new Account("three", 3);
Account account4 = new Account("four", 4);
Account account5 = new Account("five", 5);
Account account6 = new Account("six", 6);
Account account7 = new Account("seven", 7);
Account account8 = new Account("eight", 8);
Account account9 = new Account("nine", 9);
Account account10 = new Account("ten", 10);
Account account11 = new Account("eleven", 11);
Account account12 = new Account("twelve", 12);
Account account13 = new Account("thirteen", 13);
Account account14 = new Account("fourteen", 14);
Account account15 = new Account("fifteen", 15);
tree.insert(account8);
tree.insert(account4);
tree.insert(account12);
tree.insert(account2);
tree.insert(account6);
tree.insert(account10);
tree.insert(account14);
tree.insert(account1);
tree.insert(account3);
tree.insert(account5);
tree.insert(account7);
tree.insert(account9);
tree.insert(account11);
tree.insert(account13);
tree.insert(account15);
// 노드 찾기 => 이때 오직 id 값으로 찾음
boolean result1 = tree.find(account3);
boolean result2 = tree.find(new Account("one", 16));
System.out.println(result1); // true
System.out.println(result2); // false
// 삭제하기
tree.delete(account4);
// 디버깅
tree.display(account8);
tree.display(account6);
tree.display(account5);
위 소스를 그림으로 보자면 아래와 같습니다.
출력결과
true
false
좌측 자식 : Account{name='six', id=6} // 8번
우측 자식 : Account{name='twelve', id=12} // 8번
좌측 자식 : Account{name='five', id=5} // 6번
우측 자식 : Account{name='seven', id=7} // 6번
좌측 자식 : Account{name='two', id=2} // 5번
우측 자식 : null // 5번