Tree

선형, 비선형 자료구조

array, list, stack, queue는 모두 선형자료구조이고 graph, tree는 비선형 자료구조이다.

Binary Tree?

먼저, 최대 2개의 자식노드를 가질 수 있는 노드들로 이루어진 트리를 이진트리라고 한다.

이진트리의 종류에는 아래와 같은 것이 있다.

• full binary tree

모든 leaf node가 같은 깊이를 가지고, 모든 non leaf node들은 2개의 자식을 가지는 트리

• complete binray tree

가장 깊은 노드를 제외한 노드들은 가능한한 많은 자식을 가져야하고, 가장 깊은 레벨에서 모든 노드들은 왼쪽부터 채워져 있어야한다.

Tree의 구현체

배열과 노드로 표현할 수 있다.

배열에서 root를 0 번지부터 시작하면 left child 는 2i+1, right child는 2i+2 이다. 자신의 부모는 (i-1)/2 에 있는 노드이다.

Node로 표현하면 Node는 자신이 가지는 값과 left, right 자식 레퍼런스를 가지고, Node의 집합으로 Tree를 이룬다.

이래는 IntNode의 구현체이다.

public class IntBTNode
{

    private int data;
    private IntBTNode left, right;


    public IntBTNode(int initialData, IntBTNode initialLeft, IntBTNode initialRight)
    {
        data = initialData;
        left = initialLeft;
        right = initialRight;
    }

    public int getData( )
    {
        return data;
    }

    public IntBTNode getLeft( )
    {
        return left;
    }

    public int getLeftmostData( )
    {
        if (left == null)
            return data;
        else
            return left.getLeftmostData( );
    }

    public int getRightmostData( )
    {
        if (right == null)
            return data;
        else
            return right.getRightmostData( );
    }

    public IntBTNode getRight( )
    {
        return right;
    }

    public IntBTNode removeLeftmost( )
    {
        if (left == null)
            return right;
        else
        {
            left = left.removeLeftmost( );
            return this;
        }
    }

    public IntBTNode removeRightmost( )
    {
        if (right == null)
            return left;
        else
            return right.removeRightmost( );
    }

    public void setData(int newData)
    {
        data = newData;
    }

    public void setLeft(IntBTNode newLeft)
    {
        left = newLeft;
    }

    public void setRight(IntBTNode newRight)
    {
        right = newRight;
    }

    final int PRE_ORDER = 0;
    final int IN_ORDER = 1;
    final int POST_ORDER = 2;

    public void travel(IntBTNode cursor, int travelType){

        if(travelType == PRE_ORDER){
            System.out.println(cursor.data);
        }
        travel(cursor.left);
        if(travelType == IN_ORDER){
            System.out.println(cursor.data);
        }
        travel(cursor.right);
        if(travelType == POST_ORDER){
            System.out.println(cursor.data);
        }

    }

}

트리 탐색 순서

트리 탐색 순서에는 pre, in, post order이 있다. 아래는 각 탐색이 어떻게 이루지는지에 대한 코드이다.

    public void travel(IntBTNode cursor, int travelType){

        if(travelType == PRE_ORDER){
            System.out.println(cursor.data);
        }
        travel(cursor.left);
        if(travelType == IN_ORDER){
            System.out.println(cursor.data);
        }
        travel(cursor.right);
        if(travelType == POST_ORDER){
            System.out.println(cursor.data);
        }

    }

Time Complexity : O(n)

노드의 갯수만큼 탐방하기 때문에 O(n)이다. 즉 세 가지 탐방 모두 차이는 없다.

Space Complexity : O(h)

depth 만큼 Stack에 쌓이기 때문에 O(h)이다. 다만 최악의 경우, 노드가 일렬로 늘어선 경우에는 h = n이기에 O(n)이 된다. 즉 세 가지 탐방 모두 차이는 없다.

Stack이 아닌 Heap관점에 보자면 각 트리순회에서 작업이 일어나는 공간에서 malloc()하고 바로 free()해주면 동적으로 할당된 객체는 쌓이지 않게 되기에 고려하지 않아도 된다.
만약 다음 깊이의 노드가 malloc()한 메모리를 반드시 사용해야 한다면 사실 무조건 pre-order를 사용해야 될 것이다.

결국 스택영역만 바라보았을 때 O(h)의 공간복잡도를 가지게 된다.

binary search tree

이진 트리의 원소들이 원소의 값에 대한 규칙의 가지고 정렬된 트리를 이진탐색 트리라고 한다.

이진탐색 트리는 다음과 같은 특징을 가진다.

1. 각 노드는 고유의 데이터 값을 가진다.
2. 트리 안의 키 값은 비교될 수 있다.
3. 각 노드 안의 키 값은 오른쪽 서브트리의 모든 노드의 값보다 작고, 왼쪽 서브트리의 모든 노드의 값 보다 커야한다.

이진 탐색 트리는 원소를 추가하는 add(), 원소를 삭제하는 remove()의 기능을 가진다.

add(int element)

add는 먼저 element가 들어갈 수 있는 위치를 찾는다. 현재 노드의 값이 element보다 크면 왼쪽으로, 노드의 값이 element보다 작으면 오른쪽으로 이동하여 terminal노드로 간다. terminal 노드의 값보다 작으면 왼쪽, 크다면 오른쪽에 자식으로 추가된다.

아래는 구현한 코드이다.

    public void add(int element)
    {
        IntBTNode cursor = root;
        IntBTNode node = new IntBTNode(element, null, null);
        boolean done = false;

        if(root == null){
            root = node;
        }else{
            while(!done){
                if(element < cursor.getData()){
                    if(cursor.getLeft() == null){
                        cursor.setLeft(node);
                        done = true;
                    }else{
                        cursor = cursor.getLeft();
                    }
                }else{
                    if(cursor.getRight() == null){
                        cursor.setRight(node);
                        done = true;
                    }else{
                        cursor = cursor.getRight();
                    }
                }
            }
        }
    }

remove(int target)

element에 해당하는 노드를 제거한다.
먼저 element값을 가지는 노드를 찾는다.
이후 다음과 같은 경우가 있다.

1. 값을 찾지 못하였을 경우
   아무런 연산을 수행하지 않는다.

2. element가 root 노드이며 왼쪽 자식이 없는 경우
   root의 오른쪽 자식을 root로 삼는다.

3. element가 internel 노드이며 왼쪽 자식이 없는 경우
   element의 오른쪽 subtree를 자신의 위치로 끌어온다.

4. element가 왼쪽 자식이 있는 경우
   왼쪽 subtree의 rightmost 값을 element에 복사하고, rightmost를 제거한다.

아래는 구현된 코드이다.

    private boolean remove(int target)
    {
        // Student will replace this return statement with their own code:
        IntBTNode cursor;
        IntBTNode parentOfCursor;
        cursor = root;
        parentOfCursor = root;
        boolean done = false;

        if(cursor == null)
            return false;

        while(!done){
            if(target < cursor.getData()){
                if(cursor.getLeft() == null){
                    return false;
                }else{
                    parentOfCursor = cursor;
                    cursor = cursor.getLeft();
                }
            }else if(target > cursor.getData()){
                if(cursor.getRight() == null){
                    return false;
                }else{
                    parentOfCursor = cursor;
                    cursor = cursor.getRight();
                }
            }else if(target == cursor.getData()){
                done = true;
            }
        }

        if(cursor == root && cursor.getLeft() == null){
            root = cursor.getRight();
            return true;
        }else if(cursor != parentOfCursor && cursor.getLeft() == null){
            if(cursor == parentOfCursor.getLeft()){
                parentOfCursor.setLeft(cursor.getRight());
            }else{
                parentOfCursor.setRight(cursor.getRight());
            }
            return true;
        }else if(cursor != null && cursor.getLeft() != null){
            cursor.setData(cursor.getLeft().getRightmostData());
            cursor.setLeft(cursor.getLeft().removeRightmost());
            return true;
        }

        return false;
    }