개발/자료구조
[자료구조] 트리(Tree)
난중후니
2023. 1. 29. 17:39
728x90
반응형
트리(Tree) 구조
- 트리: Node를 이용해서 Node간의 순환이 발생하지 않게 구성한 데이터 구조입니다.
- 탐색(검색) 알고리즘 구현을 위해 많이 사용됩니다.
ex) 트리 구조
ex) 순한되는 경우
용어
- Node(노드): 트리에서 데이터를 저장하는 기본 요소입니다.
- Root Node: 가장 상위의 노드 입니다.
- Level: 가장 최상단에 위치한 노드를 Level 0으로 하였을 때 하위 연결된 노드의 깊이를 나타냅니다.
- Parent Node: 어떤 노드의 상위 레벨에 연결된 노드입니다.
- Child Node: 어떤 노드의 다음 레벨에 연결된 노드입니다.
- Leaf Node(Terminal Node): Child Node가 하나도 없는 노드입니다.
- Sibling (Brother Node): 동일한 Parent Node를 가진 노드입니다.
- Depth: 트리에서 Node가 가질 수 있는 최대 Level 입니다.
이진 트리와 이진 탐색 트리(Binary Search Tree)
- 이진 트리: 노드의 ChildNode(자식노드)가 최대 2개인 트리입니다.
- 이진 탐색 트리(Binary Search Tree, BST): 작은 값은 왼쪽 노드, 큰 값은 오른쪽 노드에 값을 가지고 있습니다.
ex)
노드 클래스 만들기
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: Node가 하나도 없는 경우
if(this.head == null){
this.head = Node(data);
}else {
// Case: Node가 하나 이상 들어가 있는 경우
Node findNode = this.head;
while (true){
// Case2-1: 현재 Node의 왼쪽에 Node가 들어가야 할 때
if (data < findNode.value){
if (findNode.left != null){
findNode = findNode.left;
}else{
findNode.left = new Node(data);
break;
}
}else if (data > findNode.value){
// Case2-2: 현재 Node의 오른쪽에 Node가 들어가야 할 때
if (findNode.right != null){
findNode = findNode.right;
}else{
findNode.right = new Node(data);
break;
}
}
}
}
return true;
}
}
// 이진 탐색 트리
public Node search(int data){
// Case1: Node가 존재하지 않는 경우
if(this.head == null){
return null;
}else{ // Case2: Node가 하나 이상 있을 때
Node findNode = this.head;
while (findNode != null){
if(findNode.value == data){
return findNode;
}else if(data < findNode.value){
findNode = findNode.left;
}else if(data > findNode.value){
findNode = findNode.right;
}
}
return null;
}
}
}이진 탐색 트리 삭제
Leaf Node 삭제
- Leaf Node: Child Node가 없는 노드입니다.
- 삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 합니다.
ex)
Child Node가 하나인 Node 삭제
- 삭제할 Node의 Parent가 삭제할 Node의 Child Node를 가리키도록 합니다.
null
Child Node가 2 개인 Node 삭제
- 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 합니다.
- 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 합니다.
ex) 삭제할 Node의 오른쪽 자식 중 가장 작은 값(3)을 삭제할 Parent Node(2)를 대체 하는 예제입니다.
public boolean delete(int value){
boolean searched = false;
Node currParentNode = this.head;
Node currNode = this.head;
// Case1: Node가 없는 경우
if(this.head == null){
return false;
}else{ // Case2: Node가 하나만 있고 해당 Node가 삭제할 Node 인 경우
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 에는 해당 데이터를 가지고 있는 Node를 가지고 있습니다.
// currParentNode 에는 해당 데이터를 가지고 있는 Node의 부모 Node를 가지고 있습니다.
// Case1: 삭제할 Node가 Leaf Node인 경우
if(currNode.left == null && currNode.right == null){
if(value < currParentNode.value){
currParentNode.left = null;
currNode = null;
}else{
currParentNode.right = null;
currNode = null;
}
}else if(currNode.left != null && currNode.right == null){ // Case2-1: 삭제할 Node가 Child Node를 한 개 가지고 있을 경우(왼쪽에 Child Node가 있을 경우)
if(value < currParentNode.value){
currParentNode.left = currNode.left;
currNode = null;
}else{
currParentNode.right = currNode.right;
currNode = null;
}
return true;
}else if(currNode.left == null && currNode.right != null){ // Case2-2: 삭제할 Node가 Child Node를 한 개 가지고 있을 경우(오른쪽에 Child Node가 있을 경우)
if(value < currParentNode.value){
currParentNode.left = currNode.right;
currNode = null;
}else{
currParentNode.right = currNode.left;
currNode = null;
}
return true;
}else{ // Case3-1: 삭제할 Node가 Child Node를 두 개 가지고 있는 경우, ()
// 삭제할 Node가 부모 Node의 왼쪽에 있는 경우
if(value < currParentNode.value){
Node changeNode = currNode.right;
Node changeParentNode = currNode.right;
while(changeNode.left != null){
changeParentNode = changeNode;
changeNode = changeNode.left;
}
// 여기까지 실행되면 changeNode에는 삭제할 Node의 오른쪽 Node 중에서
// 가장 작은 값을 가진 Node가 들어 있음
if(changeNode.right != null{ // Case3-1-2: changeNode의 child Node가 있는 경우
changeParentNode.left = changeNode.right;
}else{ // Case3-1-1: changeNode의 child Node가 없는 경우
changeParentNode.left = null;
}
// currParentNode의 왼쪽 Child Node에 삭제할 Node의 오른쪽 자식 중
// 가장 작은 값을 가진 changeNode를 연결
currParentNode.left = changeNode;
// parentNode의 왼쪽 Child Node가 현재, changeNode이고
// changeNode의 왼쪽/오른쪽 Child Node를 모두 삭제 할 currNode의 기존 왼쪽/오른쪽 Node로 변경
changeNode.right = currNode.right;
changeNode.left = currNode.left;
currNode = null;
}else{
Node changeNode = currNode.right;
Node changeParentNode = currNode.right;
while(changeNode.left != null){
changeParentNode = changeNode;
changeNode = changeNode.left;
}
// 여기까지 실행되면 changeNode에는 삭제할 Node의 오른쪽 Node 중에서
// 가장 작은 값을 가진 Node가 들어 있음
if(changeNode.right != null{ // Case3-1-2: changeNode의 child Node가 있는 경우
changeParentNode.left = changeNode.right;
}else{ // Case3-1-1: changeNode의 child Node가 없는 경우
changeParentNode.left = null;
}
// currParentNode의 왼쪽 Child Node에 삭제할 Node의 오른쪽 자식 중
// 가장 작은 값을 가진 changeNode를 연결
currParentNode.right = changeNode;
// parentNode의 왼쪽 Child Node가 현재, changeNode이고
// changeNode의 왼쪽/오른쪽 Child Node를 모두 삭제 할 currNode의 기존 왼쪽/오른쪽 Node로 변경
changeNode.right = currNode.right;
changeNode.left = currNode.left;
currNode = null;
}
return true;
}
}시간 복잡도 (탐색시)
- depth(트리의 높이)를 h라고 표기한다면 O(h)
- n개의 노드를 가진다면 h = log2n 에 가까우므로 시간 복잡도는 O(logn)
-> 한 번 실행시마다 50%의 실행할 수도 있는 명령을 제거한다는 의미입니다. 즉 한번 수행마다 50%의 실행시간을 단축시킬 수 있다는 것을 의미합니다.
728x90
반응형