[자료구조] 자바 에서의 트리 #1

[자료구조] 자바 에서의 트리 #1

트리 구조

Node 와 Branch 를 이용해서 노드간에 사이클이 이루어지지 않도록 구성한 데이터 구조이다.

- 트리 중 이진 트리(Binary Tree) 형태의 구조가 탐색(검색) 알고리즘 구현을 위해 많이 이용된다.

용어

- Node : 트리에서 데이터를 저장하는 기본 요소 이다.(데이터와 연결된 다른 노드에 대한 Branch 정보 포함 )

- Root Node : 트리의 가장 위에 있는 노드이다.

- Level : 최상위 노드(Root Node)를 Level 0 이라고 했을 때, 특정 노드가 최상위 노드로부터 하위 Branch 로 연결되어 있는 깊이를 의미한다.

- Parent Node : 어떤 노드의 이전 레벨에 연결된 노드

- Child Node : 어떤 노드의 하위 레벨에 연결된 노드

- Leaf Node : Child Node 를 하나도 가지고 있지 않은 노드

- Brother Node : 동일한 Parent Node 를 가지고 있는 두 개(또는 그 이상의 갯수)의 노드

- Depth : 트리에서 Node 가 가질 수 있는 최대 Level(최상위 노드로 부터 가장 멀리 떨어진 하위 Branch 로 연결된 Node 의 Level)

이진 트리와 이진 탐색 트리

- 이진 트리 : 각 노드의 최대 Branch 가 2 인 트리

- 이진 탐색 트리 : (Binary Search Tree : BST) : 이진 트리에 아래와 같은 추가적인 조건이 있는 트리

* 왼쪽 노드는 부모 노드 보다 작은 값, 오른쪽 노드는 부모 노드보다 큰 값을 가지고 있다.

이진 탐색 트리의 장점과 주요 용도

- 주요 용도 : 데이터 검색(탐색)

- 장점 : 탐색 속도를 개선할 수 있다.

* 숫자의 경우 루트 노드부터 시작하여, 비교를 통해 빠르게 찾고자 하는 노드 데이터를 탐색 할 수 있다.

- 이진 트리에서 각 노드는 왼쪽 Branch, 오른쪽 Branch 를 지칭하는 주소를 가지고 있다.

- 내부 구현의 경우 연결 리스트 형태로 구현해 볼 수 있다.

자바로 직접 코딩해보자.

자바에서는 TreeSet, TreeMap 클래스에서 이진 트리구조의 기능을 제공해주므로 편하게 이진 트리 구조를 이용할 수 있지만, 그래도 더 정확한 구조 이해를 위해 직접 코딩 해보자.

우선 노드로 사용할 객체 클래스를 만들어준다.

- Node.java

public class Node { private int value; private Node left; private Node right; public Node(int value) { this.value = value; this.left = null; this.right = null; } public Node getLeft() { return left; } public Node getRight() { return right; } public int getValue() { return value; } public void setLeft(Node left) { this.left = left; } public void setRight(Node right) { this.right = right; } }

- value 에 대한 setter 메소드의 경우 노드를 생성할 시 생성자의 파라미터 값으로 가져오므로 생략하였다.

- left, right 필드에 각각 이진 탐색 트리의 조건에 해당되는 노드의 객체 참조값이 적재될 것이다.

이제 이진 트리 구조로서 각 노드들을 관리해주기 위한 클래스를 만들어주자.

- BSTMgmt.java

public class BSTMgmt { private Node head; public BSTMgmt(Node head) { this.head = head; } public void insert(int value) { Node currentNode = this.head; while(true) { if(value < currentNode.getValue()) { if(currentNode.getLeft() != null) { currentNode = currentNode.getLeft(); } else { currentNode.setLeft(new Node(value)); System.out.println("값이 정상적으로 삽입 되었습니다."); System.out.println(); break; } } else { if(currentNode.getRight() != null) { currentNode = currentNode.getRight(); } else { currentNode.setRight(new Node(value)); System.out.println("값이 정상적으로 삽입 되었습니다."); System.out.println(); break; } } } } public void search(int value) { Node currentNode = this.head; boolean search = false; while(currentNode != null) { if(currentNode.getValue() == value) { search = true; break; } else if(value < currentNode.getValue()) { currentNode = currentNode.getLeft(); } else currentNode = currentNode.getRight(); } if(search) { System.out.println(value + " 값이 존재합니다. "); System.out.println(); } else { System.out.println("값이 존재하지 않습니다."); System.out.println(); } } public boolean delete(int value) { boolean searched = false; Node currentNode = this.head; Node parent = this.head; while (currentNode != null){ if(currentNode.getValue() == value) { searched = true; break; } else if(value < currentNode.getValue()) { parent = currentNode; currentNode = currentNode.getLeft(); } else { parent = currentNode; currentNode = currentNode.getRight(); } } if(searched == false) return false; if(currentNode.getLeft() == null && currentNode.getRight() == null) { if(value < parent.getValue()) parent.setLeft(null); else parent.setRight(null); } if(currentNode.getLeft() != null && currentNode.getRight() == null) { if(value < parent.getValue()) parent.setLeft(currentNode.getLeft()); else parent.setRight(currentNode.getLeft()); } else if(currentNode.getLeft() == null && currentNode.getRight() != null) { if(value < parent.getValue()) parent.setLeft(currentNode.getRight()); else parent.setRight(currentNode.getRight()); } if(currentNode.getLeft() != null && currentNode.getRight() != null) { Node changeNode = null; Node changeNode_Parent = null; if(value < parent.getValue()) { changeNode = currentNode.getRight(); changeNode_Parent = currentNode.getRight(); while(changeNode.getLeft() != null) { changeNode_Parent = changeNode; changeNode = changeNode.getLeft(); } if(changeNode.getRight() != null){ changeNode_Parent.setLeft(changeNode.getRight()); } else changeNode_Parent.setLeft(null); parent.setLeft(changeNode); changeNode.setLeft(currentNode.getLeft()); if(currentNode.getRight() == changeNode) { changeNode.setRight(currentNode.getRight()); } } else { changeNode = currentNode.getRight(); changeNode_Parent = currentNode.getRight(); while(changeNode.getLeft() != null) { changeNode_Parent = changeNode; changeNode = changeNode.getLeft(); } if(changeNode.getRight() != null) { changeNode_Parent.setLeft(changeNode.getRight()); } else changeNode_Parent.setLeft(null); parent.setRight(changeNode); changeNode.setLeft(currentNode.getLeft()); if(currentNode.getRight() == changeNode) { changeNode.setRight(currentNode.getRight()); } } currentNode = null; parent = null; } return true; } }

코드가 상당히 길다

각 메소드 마다 하나씩 떼서 살펴보자.

* 우선 필드 선언과 생성자 작성 코드이다.

private Node head; public BSTMgmt(Node head) { this.head = head; }

- Node 객체 head 를 선언해주고 생성자에서는 Node 객체를 파라미터로 받은 다음, 해당 객체를 head 에 적재해주었다.

- 이를 통해 이진 트리의 루트 노드를 생성해준다.

* 다음은 데이터 삽입 코드이다.

public void insert(int value) { Node currentNode = this.head; while(true) { if(value < currentNode.getValue()) { if(currentNode.getLeft() != null) { currentNode = currentNode.getLeft(); } else { currentNode.setLeft(new Node(value)); System.out.println("값이 정상적으로 삽입 되었습니다."); System.out.println(); break; } } else { if(currentNode.getRight() != null) { currentNode = currentNode.getRight(); } else { currentNode.setRight(new Node(value)); System.out.println("값이 정상적으로 삽입 되었습니다."); System.out.println(); break; } } } }

- Node 객체 currentNode 에 루트 노드 객체를 적재해 줌으로서 루트 노드에서 부터 트리를 탐색 할 수 있게 했다.

- 반복문 내부에서 메소드의 파라미터로 입력받은 value 변수와 현재 노드(currentNode) 의 데이터 값을 비교 하여

현재 노드의 데이터가 클 경우 트리의 왼쪽으로 이동할 수 있게 하였고 , 반대로 작을 경우 트리의 오른쪽으로 이동할 수 있게끔 하였다.

- value 값이 현재 노드보다 작음과 동시에 현재 노드의 왼쪽 노드가 비어있지 않다면 , 계속해서 트리의 왼쪽 노드로 이동 한다.

- value 값이 현재 노드보다 작음과 동시에 현재 노드의 왼쪽 노드가 비어있다면 , 왼쪽 노드에 value 값을 데이터로 하는 노드 객체를 생성 해줌과 동시에, 현재 노드의 왼쪽 Child Node 로서 객체 참조 를 해주고 반복문을 끝낸다.

- value 값이 현재 노드보다 크거나 같음과 동시에 현재 노드의 오른쪽 노드가 비어있지 않다면 , 계속해서 트리의 오른쪽 노드로 이동 한다.

- value 값이 현재 노드보다 크거나 같음과 동시에 현재 노드의 오른쪽 노드가 비어있다면 , 오른쪽 노드에 value 값을 데이터로 하는 노드 객체를 생성 해줌과 동시에, 현재 노드의 오른쪽 Child Node 로서 객체 참조 를 해주고 반복문을 끝낸다.

* 다음은 데이터 검색 코드이다.

public void search(int value) { Node currentNode = this.head; boolean search = false; while(currentNode != null) { if(currentNode.getValue() == value) { search = true; break; } else if(value < currentNode.getValue()) { currentNode = currentNode.getLeft(); } else currentNode = currentNode.getRight(); } if(search) { System.out.println(value + " 값이 존재합니다. "); System.out.println(); } else { System.out.println("값이 존재하지 않습니다."); System.out.println(); } }

- 삽입 메소드와 같이 루트 노드부터 시작 할 수 있게 currentNode 객체를 생성해주었다.

- boolean 타입의 search 변수를 false 값으로 선언해주고 반복문을 수행 한다.

- 현재 노드가 존재하는 동안 입력 받은 값과 현재 노드의 데이터 값을 비교 한다.

- 비교 결과 데이터가 일치할 경우 해당 데이터를 가지고 있는 노드 객체를 찾은 것 이므로 search 변수를 true 로 바꿔주고 반복문을 끝낸다.

- 비교 결과 현재 노드의 데이터가 value 보다 클 경우, 비교 노드의 위치를 현재 노드의 왼쪽 Child Node 로 변경 해준다.

- 비교 결과 현재 노드의 데이터가 value 보다 작거나 같을 경우, 비교 노드의 위치를 현재 노드의 오른쪽 Child Node 로 변경 해준다.

- 반복문이 끝난 이후 search 변수의 값에 따라 조건문을 실행해준다.

* 대망의 삭제 메소드는 2편에서 알아보자.

from http://evan-development.tistory.com/125 by ccl(A) rewrite - 2021-11-28 02:00:39