트리구조
- 트리는 노드와 연결을 할 수 있는 브랜치를 이용해서 사이클을 이루지 않도록(순회하지 않도록) 구성한 데이터 구조이다.
- 트리는 넓은 범위로 정의를 한 것이고, 그중에서 익혀야 할 구조는 이진트리 구조이다. (탐색 알고리즘을 구현할 때 꼭 사용된다.)
알아둘 용어
- 노드 : 트리에서 데이터를 저장하는 기본 요소
- 루트 노드 : 최상단 노드
- 이진트리 : 노드의 최대 브랜치가 두 개이다. (두 개의 가지를 가지고 있다.)
- 이진 탐색 트리 : 왼쪽 노드는 윗 노드의 값보다 작은 값, 오른쪽 노드는 윗 노드의 값보다 큰 값이 들어간다.
- 어떤 노드의 상위 노드 → 부모 노드 / 어떤 노드의 하위 노드 → 자식 노드
- 최상단에 위치한 노드는 Level 0 , 두 번째는 Level 1 등 각각의 레벨에 번호를 붙인다.
- Depth : 트리에서 노드가 가질 수 있는 최대 Level (밑으로 얼마나 뻗어있느냐)
- 형제 노드 : 동일한 부모 노드를 가진 노드
- Leaf Node : 자식 노드가 하나도 없는 노드
이진 탐색 트리
이진트리와 정렬된 배 열간의 비교?
- 배열은 원하는 값을 찾으려면 값이 나올 때까지 돌아야 한다.
- 이진트리는 노드를 탐색해서 효율적으로 값을 검색한다.
이진 탐색 트리 구조/삽입/탐색 구현해보기
public class NodeMgmt{
Node head = null;
public class Node{
Node left; //각각 오른쪽 왼쪽을 가리키는 브랜치를 가진다.
Node right;
int value;
public Node(int data){
this.value = data;
this.left = null;
this.right = null;
}
}
}
데이터 넣는 메서드 구현해보기
트리구조는 생각하지 못한 케이스가 많기 때문에 서브 케이스를 만들어서 각각을 구현하는 방식으로 구현하면 좋다.
public boolean insertNode(int data){
//CASE1: 노드가 하나도 없을때
if (this.head==null){
this.head = new Node(data); //노드를 새로 만들어준다.
} else{
//CASE2: Node 가 하나 이상 있을때
Node findNode = this.head; //노드를 가져와서 브랜치를 연결해준다.
while(true){
// CASE 2-1 : 현재 Node의 왼쪽에 Node가 들어가야 할때 (값이 작을때)
if (data < findNode.value){
if(findNode.left!=null){
findNode = findNode.left; //노드가 존재하면 밑으로 점점 내려오면서 값을 넣어준다.
}else{
findNode.left = new Node(data);
break;}
// CASE 2-2 : 현재 Node 의 오른쪽에 Node가 들어가야 할때
} else //값이 부모 노드보다 더 클때
{if(findNode.right != null){
findNode = findNode.right;
}else{
findNode.right = new Node(data);
break;
}
}
}
return true;
}
}
}
// 밑으로 내려가면서 연결/혹은 삽입 해준다.
- 순서를 정리해보자
- 이진트리를 구현할 때, 최상위 노드를 만들어주고 각 노드별로 왼쪽, 오른쪽을 가리키는 브랜치와 데이터를 넣을 객체 변수를 선언해준다.
- 값을 저장할 시에는 만약에 루트 노드가 존재하지 않는다면 루트 노드에 새 노드를 참조시켜주고, 존재한다면 밑으로 내려오면서 값을 저장한다.
- 밑으로 내려오는 로직은 값이 부모 노드보다 작으면 while문으로 각 브랜치로 내려와 노드가 존재한다면 참조시켜주고 존재하지 않는다면 연결해주는 식으로 노드가 존재하지 않을 때까지 Level을 늘리며 내려간다.
탐색 메서드 구현해보기
데이터를 가진 노드가 있는지/없는지를 체크하고 있으면 해당 노드를 리턴하도록 구현한다.
마찬가지로 각각의 케이스를 나눠서 구현하면 좋다.
public Node search(int data){
if(this.head==null){ //트리가 비어있다면 null을 반환한다.
return null;
}else{
Node findNode = this.head;
while(findNode !=null){ //노드가 존재한다면 탐색을 실행한다.
if(findNode.value == data){ //노드의 데이터가 검색을 원하는 데이터와 값이 같다면
return findNode;
}else if(data < findNode.value){ //데이터가 작다면 왼쪽 브랜치로 넘어가서 반복한다.
findNode = findNode.left;
} else{
findNode = findNode.right; //더 크다면 오른쪽 브랜치로 넘어가서 반복한다.
}
}
return null; //탐색했지만 없다면 null을 반환한다.
}
}
}
이진 탐색 트리의 노드 삭제법
자식 노드가 없는 Leaf Node의 삭제
- 해당 노드의 부모 노드의 브랜치를 끊어버리면 된다.
자식 노드가 하나인 부모노드 삭제
- 해당 노드의 부모 노드의 브랜치를 해당 노드의 자식 노드로 연결해준다.
자식 노드가 두 개인 부모 노드 삭제
- 삭제할 노드의 오른쪽 노드에서 가장 왼쪽에 있는 (가장 값이 작은) 연결한다.
이진 탐색 트리 삭제 구현해보기
각각의 케이스로 나눠서 구현해보자. (삭제할 노드가 존재하는지도 체크해야 한다.)
삭제를 할 노드를 탐색하는 로직을 먼저 구현한다.
public boolean deleteNode(int value){
boolean searched = false;
Node currParentNode = this.head;
Node currNode = this.head;
// 노드가 하나도 없을때
if(this.head ==null){
return false;
}
// 노드가 하나만 있고, 해당 노드가 삭제할 노드일때
else {
if(this.head.value == value && this.head.left == null && this.head.right==null){
this.head = null;
return true;
}
while(currNode !=null){
if(currNode.value = value){
searched = true;
break;
}else if(value< currNode.value){
currParentNode = currNode; //값이 일치하지 않고 작다면 왼쪽으로 내려간다.
currNode = currNode.left
}else {
currParentNode = currNode; //크다면 오른쪽으로 간다.
currNode = currNode.right;
}
}
if(searched == false){
return false;
}
}
}
}
// 여기까지 실행된다면 currNode 에는 해당 데이터를 가지고 있는 노드가 담겨있다.
// currParentNode 에는 해당 노드의 부모 노드가 참조된다.
삭제할 노드가 Leaf Node 인 경우
- 단순히 삭제할 노드의 부모 노드의 자식 노드 연결을 끊어버리면 된다.
if(currNode.left == null && currNode.right) {
if(value<currParentNode.value){ //
currParentNode.left =null; //branch 연결을 끊어준다.
currNode = null;
}else{
currParentNode.right =null;
currNode = null;
}
return true;
}
삭제할 노드가 자식 노드를 한 개만 가지고 있을 경우
단순히 부모 노드의 연결을 자식 노드로 바꿔주면 된다.
- 삭제할 노드의 부모 노드의 데이터와 해당 노드의 데이터를 비교한다.
- 해당 노드의 자식 노드가 왼쪽/오른쪽에 있는지 판단해 부모 노드의 데이터보다 값이 작다면 왼쪽에 , 크다면 오른쪽에 브랜치를 연결해준다.
// 자식 노드가 왼쪽에 있을경우
else if ( currNode.left!=null && currNode.right==null ){
if(value < currParentNode.value){ //부모 노드보다 작다면 왼쪽에 연결한다.
currParentNode.left = currNode.left;
currNode = null;
}
else{
currParentNode.right = currNode.left;
currNode = null;
}
return true;
// 자식 노드가 오른쪽에 있을경우
else if ( currNode.left ==null && currNode.right !=null ){
if(value < currParentNode.value){ //단순히 반대로 실행한다.
currParentNode.left = currNode.right;
currNode = null;
}else{
currParentNode.right = currNode.right;
currNode = null;
}
return true;
삭제할 노드가 자식 노드를 두 개 가지고 있을 경우
- 삭제할 노드의 오른쪽 자식 중, 가장 작은 값을 삭제할 노드의 부모 노드가 가리키도록 한다.
- 삭제할 노드가 부모 노드의 왼쪽에 있고, 삭제할 노드의 오른쪽 자식 중 , 가장 작은 값을 가진 노드의 자식 노드가 없을 때
- 삭제할 노드가 부모 노드의 왼쪽에 있고, 삭제할 노드의 오른쪽 자식 중 , 가장 작은 값을 가진 노드의 오른쪽에 자식 노드가 있을 때
- 가장 작은 값을 가진 노드의 자식 노드가 왼쪽에 있는 경우는 없다. 왜냐하면 왼쪽 노드가 있다는 것은 해당 노드보다 더 작은 값을 가진 노드가 있다는 뜻이기 때문이다.
이해하기 어렵다면 각각의 케이스를 외워버리는 것도 좋은 방법이다.
해당 부분은 너무 복잡해서 나중에 한번 더 수강할 예정입니다 🤔
시간 복잡도
- 트리의 depth를 h라고 한다면 O(h)
- n개의 노드를 가진다면 o(logn) ⇒ 이진트리가 균형 잡혀 있을 때의 평균 시간 복잡도이다.
- 한번 실행시마다 50%의 실행할 수도 있는 명령을 제거한다는 의미이다.
- 최악의 경우에 링크드 리스트 등과 동일한 성능을 보여준다. ( o(n))
느낀 점
- 이진트리가 무엇인지 알고는 있었으나 어떻게 구현하는지는 몰랐는데, 이번 기회가 1차적으로 구조가 이해가 되는 느낌입니다.
- 확실히 값을 저장하고 탐색할 때는 크게 힘든 게 없지만, 삭제할 때는 다른 자료구조와 달리 트리의 복잡도에 따라서 머리로만 그리는 것도 어려운 느낌입니다. 확실히 케이스가 많은 것 같습니다.
- 별개로 해당 자료구조를 구현한 자바의 트리 API들이 해당 부분들을 다 구현해놓은 상태인지 궁금합니다. 찾아봐야겠습니다 🤔
- 단순히 탐색에 좋은 자료구조라고 생각해서 무분별하게 사용하다간 다른 자료구조보다 시간 복잡도가 더 나올 수 있는 상황이 생길 것 같습니다. 특히나 값이 같거나 1차원적인 트리의 사용은 지양해야겠습니다.
'Algorithm' 카테고리의 다른 글
백준 2075번 N번째 큰 수 (자바) 풀이 (0) | 2022.12.19 |
---|---|
백준 15903번 카드 합체 놀이 (자바) 풀이 (0) | 2022.12.19 |
백준 2910번 빈도 정렬 (자바) 풀이 (0) | 2022.12.15 |
백준 1764번 듣보잡 (자바)풀이 (0) | 2022.12.15 |
해쉬 자료구조에 대해서 알아보자 🤔 (0) | 2022.12.15 |