심플하고 차분하게

1. 최소힙 구현하기

import java.util.ArrayList;

class MinHeap{
    ArrayList<Integer> tree;

    public MinHeap(){
        this.tree = new ArrayList<Integer>();
        this.tree.add(0); // dummy data
    }

    // 삽입 : (1) 트리의 가장 뒤에 삽입 (2) 삽입 위치에서부터 부모와 비교
    public void add(int data){
        this.tree.add(data);

        int curIdx = this.tree.size() - 1; // 현재 위치
        int parentIdx = curIdx / 2; // 부모 위치
        while (curIdx > 1 && tree.get(parentIdx) > tree.get(curIdx)) {
            int tmp = tree.get(parentIdx);
            tree.set(parentIdx, tree.get(curIdx));
            tree.set(curIdx, tmp);
            curIdx = curIdx / 2;
        }
    }

    // 삭제 : (1) 루트를 삭제 (2) 루트에 가장 끝 노드를 삽입 (3) 루트에서부터 비교
    public int remove(){

        if (this.tree.size() == 1){
            System.out.println("this heap is empty!");
            return -1;
        }

        // (1)-(2)
        int min = this.tree.get(1);
        int last = this.tree.remove(this.tree.size() - 1);
        this.tree.set(1, last);

        // (3)
        int curIdx = 1;
        while(true){
            int leftIdx = curIdx * 2;
            int rightIdx = curIdx * 2 + 1;
            int childIdx = -1;

            if (rightIdx < this.tree.size()) { // 자식노드가 둘 다 있는 경우
                childIdx = tree.get(leftIdx) < tree.get(rightIdx) ? leftIdx : rightIdx;
            } else if (leftIdx < this.tree.size()) { // 자식노드가 하나인 경우
                childIdx = leftIdx;
            } else { // 자식이 하나도 없을 때
                break;
            }
            
            if (tree.get(curIdx) < tree.get(childIdx)){
                break;
            } else {
                int tmp = tree.get(curIdx);
                tree.set(curIdx, tree.get(childIdx));
                tree.set(childIdx, tmp);
                curIdx = childIdx;
            }
        }

        return min;
    }
}

2. 최대힙 구현하기

import java.util.ArrayList;

class MaxHeap{
    ArrayList<Integer> tree;

    public MaxHeap(){
        this.tree = new ArrayList<Integer>();
        this.tree.add(0); // dummy data
    }

    // 삽입 : (1) 트리의 가장 뒤에 삽입 (2) 삽입 위치에서부터 부모와 비교
    public void add(int data){
        this.tree.add(data);

        int curIdx = this.tree.size() - 1; // 현재 위치
        int parentIdx = curIdx / 2; // 부모 위치
        while (curIdx > 1 && tree.get(parentIdx) < tree.get(curIdx)) {
            int tmp = tree.get(parentIdx);
            tree.set(parentIdx, tree.get(curIdx));
            tree.set(curIdx, tmp);
            curIdx = curIdx / 2;
        }
    }

    // 삭제 : (1) 루트를 삭제 (2) 루트에 가장 끝 노드를 삽입 (3) 루트에서부터 비교
    public int remove(){

        if (this.tree.size() == 1){
            System.out.println("this heap is empty!");
            return -1;
        }

        // (1)-(2)
        int max = this.tree.get(1);
        int last = this.tree.remove(this.tree.size() - 1);
        this.tree.set(1, last);

        // (3)
        int curIdx = 1;
        while(true){
            int leftIdx = curIdx * 2;
            int rightIdx = curIdx * 2 + 1;
            int childIdx = -1;

            if (rightIdx < this.tree.size()) { // 자식노드가 둘 다 있는 경우
                childIdx = tree.get(leftIdx) > tree.get(rightIdx) ? leftIdx : rightIdx;
            } else if (leftIdx < this.tree.size()) { // 자식노드가 하나인 경우
                childIdx = leftIdx;
            } else { // 자식이 하나도 없을 때
                break;
            }

            if (tree.get(curIdx) > tree.get(childIdx)){
                break;
            } else {
                int tmp = tree.get(curIdx);
                tree.set(curIdx, tree.get(childIdx));
                tree.set(childIdx, tmp);
                curIdx = childIdx;
            }
        }

        return max;
    }
}

1. 배열을 통한 이진트리 순회

// 배열을 통한 이진트리 구현
class BinaryTree{
    char[] arr;
    
    BinaryTree(char[] data){
    	this.arr = data;
    }
    
    public void preOrer(int idx){      
        System.out.print(arr[idx] + " ");
        
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        
        if (left < this.arr.length){
        	preOrder(left);
        }
        
        if (right < this.arr.length){
            preOrder(right);
        }
    }
    
    public void inOrder(int idx){
    	int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        
        if (left < arr.length){
           inOrder(left);
        }
        
        System.out.print(arr[idx] + " ");
        
        if (right < arr.lenght){
           inOrder(right);
        }
    }
    
    public void postOrder(int idx){
    	int left = idx * 2 + 1;
        int right = idx * 2 + 2;
        
        if (left < arr.length) {
           postOrder(left);
        }
        
        if (right < arr.length) {
           postOrder(right);
        }
        
        System.out.print(arr[idx] + " ");
    }
    
    public void levelOrder(int idx){
    	for (int i = idx; i < arr.length; i++){
        	System.out.print(arr[i] + " ");
        }
        System.out.println("");
    }
}

public class Main{
   public static void main(String[] args){
      BinaryTree bt = new BinaryTree(new char[]{'A','B','C','D','E','F','G'});
      //     A
      //   B   C
      //  D E F G
   }
}

2. 연결리스트를 통한 이진트리 순회

// 노드의 연결(연결리스트)을 통한 이진트리 구현
class Node{
    char data;
    Node left;
    Node right;
    
    Node(char data){
    	this.data = data;
    }
}

class BinaryTree{
    Node root;
    
    BinaryTree(char[] datas){
    	Node nodes[] = new Node[datas.length];
    
        // 각각의 노드를 생성
    	for (int i = 0; i < datas.length; i++){
        	nodes[i] = new Node(datas[i]);
        }
        
        // 트리 형태로 노드를 연결
        root = nodes[0];
        for (int i = 0; i < nodes.length; i++){
        	int left = i * 2 + 1;
            int right = i * 2 + 2;
            
            nodes[i].left = nodes[left];
            nodes[i].right = nodes[right];
        }
    }
    
    public void preOrder(Node node){
    	if (node == null) {
        	return;
        }
        
        preOrder(node.left);
        System.out.print(node.data + " ");
        preOrder(node.right);
    }
    
    public void inOrder(Node node){
    	if (node == null) {
        	return;
        }
    
    	inOrder(node.left);
        System.out.print(node.data + " ");
        inOrder(node.right);
    }
    
    public void postOrder(Node node){
    	if (node == null){
        	return;
        }
        
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data + " ");
    }
    
    public void levelOrder(Node node){
    	Queue<Node> queue = new LinkedList();
        queue.add(node);
        
        while (!queue.isEmpty()){
			Node cur = queue.poll();
            System.out.print(cur.data + " ");
            
            if (cur.left != null) {
            	queue.offer(cur.left);
            }
            
            if (cur.right != null) {
            	queue.offer(cur.right);
            }
        }
    }
}

public class Main{
   public static void main(String[] args){
      BinaryTree bt = new BinaryTree(new char[]{'A','B','C','D','E','F','G'});
      //     A
      //   B   C
      //  D E F G
   }
}

3. 가중치가 있는 포화이진트리의 루트~리프까지의 가중치 총합을 동일하게 만드는 최소합

BinaryTree{
    int h; //높이
    int sum; //가중치의합
    int[] w; //가중치 배열
    
    BinaryTree(int h, int[] w){
    	this.h = h;
        this.w = new int[(int)(Math.pow(2, (h+1)))];
        
        for (int i = 2; i < this.w.length; i++){
        	this.w[i] = w[i-2];
        }
    }
    
    // 하위 좌우 중 더 큰 가중치에 맞춘 후 -> 상위 좌우 중 더 큰 가중치 합에 맞춘다.
    public int dfs(int h, int idx){
    	if (h == this.h){
        	res += this.w[idx]; //리프 가중치 추가
        	return this.w[idx];
        }
        
        int leftW = dfs(h + 1, idx * 2 + 1); // 좌측 서브 트리의 가중치 합
        int rightW = dfs(h + 1, idx * 2 + 2); // 우측 서브 트리의 가중치 합
        res += this.w[idx] + Math.abs(leftW - rightW); 
        return this.w[idx] + Math.max(leftW, rightW); // 서브 트리에서 더 큰 가중치 합 반환
    }
}

public class Main{

	public static void solution(int h, int[] w) {
    	BinaryTree bt = new BinaryTree(h, w);
		bt.dfs(0, 1);
        System.out.println(bt.res);
    }

	public static void main(String[] args){
    	int h = 2;
        int[] w = new int[]{1, 1, 2, 1, 3, 1};
        solution(h, w);
    }
}

 * 여기서의 탐색은 루트에서부터의 탐색으로, 이진 탐색 트리를 실제로 조회할 때는 4가지 순회 중 하나를 선택하는 것이 더 유리하다.(ex. preOrder/InOrder/....)

class Node{
    int key;
    Node left;
    Node right;
    
    Node(int key, Node left, Node right){
    	this.key = key;
        this.left = left;
        this.right = right;
    }
}

class BinarySearchTree{

    Node root;
	
    BinatySearchTree(int key){
    	this.root = new Node(key, null, null);
    }
    
    // 삽입
    public void add(int key){
    	if (root == null){
        	root = new Node(key, null, null);
        } else {
        	Node cur = this.root;
            Node pre = cur;
            
            while (cur != null) {
            	pre = cur;
            
            	if (key < cur.key){
                	cur = cur.left;
                    
                    if (cur == null){
                    	pre.left = new Node(key, null, null);
                        break;
                    }
                }
                
                if (key > cur.key){
                	cur = cur.right;
                    
                    if (cur == null) {
                    	pre.right = new Node(key, null, null);
                        break;
                    }
                }
            }
        }
    }
    
    // 삭제
    public void remove(int key){
    	// 탐색 (해당 key값을 가진 노드 탐색)
        Node cur = this.root;
        Node parent = null;
        
        while (cur != null){
        	if (cur.key == key){
            	break;
            }
            
            parent = cur;
            if (key < cur.key) {
            	cur = cur.left;
            } else {
            	cur = cur.right;
            }
        }
        
        if (cur == null){ //없을 때
        	System.out.println("BinarySearchTree doesn't have key " + key);
        }
        
        // 세가지 case에 따라 삭제 진행
        Node child = null;
        Node leftRightMax = null;
        Node ex;
        
        // case 1 : 삭제 노드가 leaf 일 때
        if (cur.left == null && cur.right == null){
        	if (cur == this.root){
            	this.root = null;
            } else {
            	if (parent.left == cur){
                	parent.left = null;
                } else {
                	parent.right = null;
                }
            }
        } 
        // case 2 : 삭제 노드에 자식이 하나 있을 때
        else if (cur.left != null && cur.right == null || cur.left == null && cur.right != null) {
        	// 자식 위치를 먼저 확인
            if (cur.left != null) {
            	child = cur.left;
            } else {
            	child = cur.right;
            }
            
            // 자식 노드를 현재 위치로 올린다.
            if (parent == null){ // = cur 가 root
            	this.root = child;
            } else {
            	if (parent.left == cur){
                    parent.left = child;
                } else {
                    parent.right = child;
                }
            }
        }
        // case 3 : 삭제 노드에 자식이 둘 있을 때
        else {
        	// 나의 좌측 노드 중 가장 큰 노드를 찾는다.
            ex = cur;
            leftRightMax = cur.left;
            
            while (now.right != null){
            	ex = leftRightMax;
            	leftRightMax = leftRightMax.right;
            }
            
            // 나의 위치에 찾은 노드를 넣어준다.
            ex.right = leftRightMax.left; // 먼저, 찾은 노드에 좌측노드가 있는 경우
            leftRightMax.left = cur.left;
            leftRightMax.right = cur.right;
            
            if (parent == null){
            	this.root = leftRightMax;
            } else {
            	if (parent.left == cur) {
                	parent.left = leftRightMax;
                } else {
                	parent.right = leftRightMax;
                }
            }
        }
    }
    
}

  1. ArrayList는 사실상 배열이고, 데이터가 늘어날 때마다 배열을 새로 만든다.  

자바 라이브러리에 들어있는 ArrayList 코드를 분석해보면 아래와 같았다.

[1] ArrayList의 디폴트 길이 10 - 그렇지만 중요한 건 실제 데이터의 양

처음 ArrayList를 생성할 때 디폴트 길이(size)는 10으로 되어 있는 걸 볼 수 있는데,

말만 디폴트이지, 생성과 동시에 데이터를 아무것도 넣지 않았다면 메모리상 실제 ArrayList의 길이는 0이다.

private static final int DEFAULT_CAPACITY = 10; //디폴트 길이

private static final Object[] EMPTY_ELEMENTDATA = {}; // 아무것도 안 들어가있다.

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 아무것도 안 들어가있다.

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA; // 아무것도 안 들어가있다.
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 아무것도 안 들어가있다.
}

>> 그렇다면 아래 코드에서 사이즈는 몇일까?

ArrayList<Integer> list = new ArrayList<>(10);
list.add(1);
list.add(2);
System.out.println(list.size());

>>> 답은 2.

-- 초기값을 지정해준다고 해도, 중요한 건 실제 데이터의 양이었다.

-- 결국 size는 지정해줘봤자 실제로 데이터가 들어간 만큼만 나온다.

-- 그런데도 지정해주는 이유는 뭘까? 이유는 ArrayList 크기를 미리 지정해두는 게, 계속해서 배열을 생성하고 복사하는 과정을 줄일 수 있기 때문이다. 

[2] 길이의 자동 변경? - 사실은 새로운 크기의 배열을 생성하고 기존걸 복사하는 것

- 아래 java.util.ArrayList의 add(E e, Object[] elementData, int s) 코드를 보면, 

- 배열 공간을 넘어설 때, Arrays.copyOf(T[] original, int newLength)로 결국 배열을 새로 생성하는 걸 볼 수 있다. 

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow(); //아래의 grow()를 보자
    elementData[s] = e;
    size = s + 1;
}
    
private Object[] grow(int minCapacity) { 
    return elementData = Arrays.copyOf(elementData, // 결국 배열을 또 만든다
                                       newCapacity(minCapacity));
}

  2. ArrayList의 데이터를 추가하고 삭제할때  

[1] 데이터를 추가할 때

- 1-[2]에서 본 것처럼 배열은 데이터를 추가할 때 공간(크기)을 벗어나면 새로운 배열을 생성하고, 복사한다.

// 끝에 삽입 시 : 배열 새로 생성 + 처음부터 끝까지 복사 + 새 데이터 추가하기
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow(); //배열 새로 생성 + 복사
    elementData[s] = e; //끝에 새로운 데이터 추가
    size = s + 1;
}

// 중간 삽입 시 : 배열 새로 생성 + 특정 index ~ 끝까지 복사 + 새 데이터 끼우기
public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow(); //배열 새로 생성 + 복사
    System.arraycopy(elementData, index, //넣을 자리부터 ~ 끝까지 데이터를 
                     elementData, index + 1, //넣을 자리 + 1 위치에 
                     s - index); //전체 사이즈에서 넣을 자리 뺀만큼 복사
    elementData[index] = element; //넣을 자리에 새로운 데이터 넣기
    size = s + 1;
}

[2] 데이터를 삭제할 때

시작하기 전에 잠시 전급하자면 ArrayList의 배열 타입은 Object[]이다.

- ArrayList를 쓸 때 정수형 데이터(int)를 boxing해야하는 경우들이 있었다.

- 예를 들어, 배열스트림-->List로 변경할때, Arrays.stream(arr).boxed().collect(Collectors.toList()) 

- 그 외에도, forEach문을 쓸 때 때때로 boxing을 해줄 때가 있었는데, 그 이유는 ArrayList의 배열 타입이 Object[]여서 였다.

이제 다시 데이터 삭제로 돌아가자.

ArrayList에서 "삭제"란 데이터를 실제로 "없앤다"기 보다는 "참조값(주소)"를 바꾸는 걸 얘기한다

>> 예를 들어, 중간 데이터를 삭제할 때는 중간 데이터 이후부터 데이터들을 앞으로 미루고,

>> 마지막 인덱스를 null로 바꿔주는 걸 볼 수 있다.

참고로 데이터를 삭제할 때에는 인자로 null 값까지도 확인을 하는데, null을 삭제해달라 요청하면 true를 반환한다.

// 실제로는 제거가 아니라, 마지막 인덱스를 null로 변경하는 것
private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i) //(처음포함)중간 인덱스를 제거하는 거라면
        System.arraycopy(es, i + 1, es, i, newSize - i); //인덱스 다음~끝을 인덱스자리에 복사
    es[size = newSize] = null; //끝 인덱스를 null로 변경
}

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: { //데이터가 있는지 없는지 확인
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i); //있으면 fastRemove()
    return true;
}

- 마찬가지로 clear도 같은 원리로 모든 데이터 위치를 null로 변경한다.

public void clear() {
    modCount++;
    final Object[] es = elementData;
    for (int to = size, i = size = 0; i < to; i++)
        es[i] = null;
}

  3. 배열이나 ArrayList를 스택을 옆으로 누인 형태로 쓸 수 있다.  

- 스택은 LIFO, 나중에 들어간 데이터를 빼주는 형태다 

- ArrayList는 추가할 때 (공간 내에서) 처음부터 순차적으로 추가하면 새로운 배열을 생성하고 카피하지 않는다. 

- ArrayList를 삭제할 때 끝부터 삭제하면 데이터를 카피하는 작업 없이 null처리만으로도 삭제가 가능하다. 

- 결국 배열이나 ArrayList도 스택처럼 사용이 가능하다는 의미이다.

  4. ArrayList 구현하기  

이제 위의 원리를 토대로 ArrayList를 다시 구현해보면 아래와 같다.

import java.util.Arrays;

class MyArray {
    int[] arr;
    
    int size; // 현재 저장된 실제 사이즈

//  배열의 초기 사이즈 설정
    MyArray(int initialSize) {
        arr = new int[initialSize];
    }

//  배열에 데이터 삽입
    // 끝에 삽입
    public void add(int data) {
        if (size == arr.length) {
            arr = Arrays.copyOf(arr, size + 1);
        }
        arr[size] = data;
        size++;
    }

    // 특정 인덱스에 삽입
    public void add(int idx, int data) {

        if (idx > arr.length - 1) {
            this.add(data);
        } else if (idx >= 0){

            int[] newArr = arr.clone();
            int newSize = size;

            if (size == arr.length){
                newArr = Arrays.copyOf(arr, size + 1);
                newSize++;
            }

            System.arraycopy(arr, idx, newArr, idx + 1, size - idx);
            newArr[idx] = data;
            arr = newArr;
            size = newSize;

        } else {
            System.out.println("Idx Error!");
        }
    }

//  배열에서 데이터 삭제
    // 특정 데이터 삭제
    public boolean remove(int data) {

        int idx = 0;
        boolean hasData = false;

        for (int i = 0; i < size; i++) {
            if (arr[i] == data) {
                idx = i;
                hasData = true;
                break;
            }
        }

        if (hasData) {
            fastRemove(idx);
        } else {
            System.out.println("해당 데이터가 없습니다.");
        }

        return hasData;
    }

    // 실질적인 삭제
    public void fastRemove(int idx) {

        int[] newArr = new int[size - 1];

        if (idx < size - 1) { //처음 또는 중간 인덱스 제거시

            int newIdx = 0;

            for (int i = 0; i < idx; i++){
                newArr[newIdx++] = arr[i];
            }

            for (int i = idx + 1; i < size; i++){
                newArr[newIdx++] = arr[i];
            }

        }else{ //마지막 인덳 제거시
            for (int i = 0; i < idx; i++){
                newArr[i] = arr[i];
            }
        }
        arr = newArr;
        size = size - 1;
    }


}