[자료구조] 자바 에서의 트리 #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<E>, TreeMap<K, V> 클래스에서 이진 트리구조의 기능을 제공해주므로 편하게 이진 트리 구조를 이용할 수 있지만, 그래도 더 정확한 구조 이해를 위해 직접 코딩 해보자.

 

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

- 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편에서 알아보자.