트리 자료구조를 직접 구현해보고 이해해보자 🤔

트리구조

• 트리는 노드와 연결을 할 수 있는 브랜치를 이용해서 사이클을 이루지 않도록(순회하지 않도록) 구성한 데이터 구조이다.
• 트리는 넓은 범위로 정의를 한 것이고, 그중에서 익혀야 할 구조는 이진트리 구조이다. (탐색 알고리즘을 구현할 때 꼭 사용된다.)

알아둘 용어

• 노드 : 트리에서 데이터를 저장하는 기본 요소
• 루트 노드 : 최상단 노드
• 이진트리 : 노드의 최대 브랜치가 두 개이다. (두 개의 가지를 가지고 있다.)
• 이진 탐색 트리 : 왼쪽 노드는 윗 노드의 값보다 작은 값, 오른쪽 노드는 윗 노드의 값보다 큰 값이 들어간다.
• 어떤 노드의 상위 노드 → 부모 노드 / 어떤 노드의 하위 노드 → 자식 노드
• 최상단에 위치한 노드는 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차원적인 트리의 사용은 지양해야겠습니다.