[자료구조] - 트리(Tree)[5] - 이진 트리의 구현

 

 

이진트리는 배열과 Node를 사용하여 표현할 수 있습니다.

우선 배열을 사용한 표현방법부터 알아보겠습니다.

 

 

 

 

 

 

배열을 사용한 이진트리의 표현

배열을 사용하여 이진트리를 구현한 모습은 다음과 같습니다.

 

조금 살펴보면 특징이 보이실텐데 노드의 번호와 배열의 인덱스에 어떠한 관계가 존재합니다.

 

 

 

 

 

 

 

 

노드 번호와 배열 인덱스의 관계

배열의 첫 인덱스인 0은 사용하지 않고, 루트 노드의 인덱스를 1로 설정하겠습니다.

이러한 경우 배열의 인덱스가 i인 노드 N에 대하여 다음 관계가 성립합니다.

N의 부모 노드의 인덱스는 [N/2] 입니다. (i가 1인 경우 루트 노드이므로 부모노드는 존재하지 않습니다.)
N의 왼쪽 자식은 2 x i에 존재합니다. (2 x i가 노드의 개수보다 크다면 왼쪽 자식이 존재하지 않습니다.)
N의 오른쪽 자식은 2 x i + 1에 존재합니다. (2 x i + 1이 노드의 개수보다 크다면 오른쪽 자식이 존재하지 않습니다.)

 

 

 

 

 

 

 

 

완전 이진트리의 깊이

노드의 개수가 n개인 완전 이진트리의 깊이(높이)는 다음과 같습니다.

$$[log_{2}n] + 1$$

즉 노드의 개수가 9개인 경우, 완전 이진트리의 깊이는 4가 됩니다.

 

 

 

 

 

 

 

 

 

배열을 이용한 트리의 표현의 장단점

 

장점

• 배열이므로 특정 원소에 접근하는 경우 매우 빠릅니다.
• 완전 이진트리인 경우 낭비되는 메모리 공간이 없습니다.

 

 

단점

• 완전 이진트리가 아닌 경우 메모리 낭비가 많을 수 있습니다.
• 삭제 시 위치를 이동해야 할 원소가 많은 경우 비효율적입니다.

 

 

 

 

 

 

 

 

 

연결체인(노드)을 사용한 이진트리의 표현

연결체인으로 이진트리를 구현한다면 메모리가 낭비되지 않습니다.

또한 서브트리를 통째로 바꿀 수 있기에, 삭제 시 효율적일 수 있습니다.

 

 

 

 

다음과 같이 노드를 사용하여 구현할 수 있습니다.

public class BinaryTree <T> {


   private BinaryNode<T> root;

 

 

 

 

 

노드는 다음과 같이 leftChild와 rightChild 노드를 가지고 있습니다.

public class BinaryNode<T> {

   private T element;
   private BinaryNode<T> leftChild;
   private BinaryNode<T> rightChild;

 

 

 

 

 

 

 

해당 구조는 일반 트리의 표현에서 Left Child - Right Sibling의 구현과 매우 비슷하며, 실제로 변수의 이름만 바꾼다면 동일한 구조임을 알 수 있습니다.

public class TreeNode<E> {
   private E element;
   private TreeNode<E> leftChild;
   private TreeNode<E> rightSibling;

 

 

 

 

 

 

 

 

 

 

자바로 구현

https://ttl-blog.tistory.com/703

[Java] - 자바로 이진트리(Binary Tree) 구현하기