public static void printTree(int[] arr) {
int level = 0;
int index = 0;
while (index < arr.length) {
int nodesInLevel = (int) Math.pow(2, level); // 해당 레벨의 노드 개수
for (int i = 0; i < nodesInLevel && index < arr.length; i++) {
System.out.print(arr[index] + " ");
index++;
}
System.out.println(); // 각 레벨 출력 후 줄바꿈
level++;
}
}
Linked List 표현
Linked List로 표현할 경우 좀더 효율적으로 생성이 가능하다는 장점이 있지만, 균형 이진 트리인 경우 배열로 구현하는 것이 더욱 효율적이라 생각합니다.
우선 우리가 알고 있는 java.util.LinkedList 구현체로 구현하는 것은 아닙니다.
LinkedList의 구현체 중 데이터 저장 클래스인 Node를 확인해보면 Node안은 아래 필드들로 구현되어있습니다.
E item
Node<E> next
Node<E> prev
위와 같이 이전과 이후에 대한 주소를 얻을 수 있지만 우리가 원하는 이진트리를 구현하기 위해서는 next가 leftNext와 rightNext로 나눠져야합니다.
그리하여 직접 구현한다면 아래와 같이 구현할 수 있습니다.
public static class TreeNode<E> {
private E item;
private TreeNode<E> left;
private TreeNode<E> right;
public TreeNode(E item) {
this.item = item;
}
}
public static class BinaryTree {
TreeNode<Integer> root;
public void add(Integer item) {
root = addRecursive(root, item);
}
private TreeNode<Integer> addRecursive(TreeNode<Integer> current, Integer item) {
if (current == null) {
return new TreeNode<>(item);
}
if(current.item > item) {
current.left = addRecursive(current.left, item);
} else {
current.right = addRecursive(current.right, item);
}
return current;
}
}
root를 기준으로 왼쪽은 작은값, 오른쪽은 큰값으로 셋팅되게 구현하였습니다.
검색의 성능을 높이기 위해 최소 힙, 최대 힙, 탐색 이진 트리 등등 다양한 방법으로 구성될 수 있으며,
Stack은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO( Last In First Out ) 자료구조입니다.
추상자료형( abstract data type, ADT )이며, 이는 논리적인 기능을 명시해 놓은 것이라 볼 수 있고, 이는 구현체가 이를 상속받아 구현하는 방식으로 자료형은 Stack이지만 구현은 여러 방법으로 구현할 수 있음을 의미합니다.
Stack은 Vector를 상속받아 구현을 하고 있는데 이는 Vector를 구현되 LIFO방식으로 데이터를 다룰 수 있게 다루기 위해 Stack이란 자료형이 존재한다 생각해 볼 수 있습니다.
우선 기본적인 기능을 확인해 보겠습니다.
Stack은 Vector를 상속한 ADT이기 때문에 기본적으로 Object []인 elementData로 데이터를 관리하고 있습니다.
배열의 크기는 기본적으로 10의 크기로 생성하고 있으며, resizing을 통해 많은 데이터가 들어오더라도 수용할 수 있습니다. 이렇듯 대부분의 기능은 동일하지만, 외부에서 접근할 수 있는 pop메서드를 확인해 보면 elemtnData의 Size를 확인하여 맨 마지막 데이터만을 추출할 수 있도록 구현되어 있는 것을 확인할 수 있습니다.
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
제공하는 기능
Method
기능
push
item을 추가합니다.
pop
최근 들어온 Element를 추출합니다.
peek
최근 들어온 Element를 확인합니다.
search
element를 조회합니다. ( Index를 반환합니다. )
사용처
그럼 Stack은 어떤 곳에서 사용하게 될까요??
웹브라우저 History 즉 뒤로가기 앞으로가기 와 같은 기능처럼 history를 쌓아두고 이를 최신 것부터 접근하는 상황이 있다면 이럴때는 Stack을 사용함으로써 편하게 관리할 수 있습니다.
또한 재귀함수와 같이 연산이 루프를 도는 방향의 알고리즘을 구현을 한다면,
최근 접근 한 것들을 접근 할 수 있는 Stack을 통해 쉽게 최근에 넣은 데이터를 꺼내 연산을 하면서 손쉽게 구현할 수 있습니다. 백준 코딩 테스트
