[DS] Tree & Binary Tree

1. Tree

트리는 비선형 자료구조로 부모와 자녀로 이루어진 계층적 관계를 가진 자료구조이다.

1) 용어

- Node: 노드. 트리를 구성하고 있는 각각의 요소를 의미한다.

- Edge: 간선. 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미하다.

- Root Node: 루트 노드. 트리 구조에서 최상위에 있는 노드 (뿌리)를 의미한다.

- Terminal Node (leaf Node): 단말 노드. 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다.

- Internal Node: 내부 노드, 비단말 노드. 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.

- degree: 차수. 자식 노드의 개수.

- height: 높이. 트리에서 루트 노드부터 가장 깊은 리프 노드까지의 길이.

- level: 레벨. 트리의 각 층, 깊이가 같은 노드 들의 집합.

2. Binary Tree

트리의 각 요소들이 최대 두개의 자녀 노드 (left child, right child)를 가지는 트리 구조의 한 종류. 루트 노드를 중심으로 두개의 서브 트리로 나누어지고 각 서브트리도 모두 이진트리인 재귀적 구조로 되어있다. 공집합도 이진 트리로 포함된다.

 

이진트리의 노드들은 기본적으로 다음의 값들로 구성되어진다.

- 노드의 값

- left child를 가리키는 포인터

- right child를 가리키는 포인터

 

이진 트리는 트리의 구조에 따라 분류된다.

1) 포화 이진 트리 (perfect binary tree)

- 모든 레벨이 꽉 찬 이진 트리.

- 모든 노드가 양쪽에 두개의 서브트리, 노드를 가지고 있어서 모든 단말 노드의 깊이가 같은 트리.

 

2) 완전 이진 트리 (complete binary tree)

- 위에서 아래로, 왼쪽에서 오른쪽으로 중간에 빠짐이 없이 순서대로 노드들이 채워진 이진 트리.

- 모든 단말 노드의 깊이의 최댓값과 최솟값의 차이가 0 또는 1이 된다.

- 포화 이진 트리처럼 모든 leaf node를 제외한 모든 노드가 2개씩의 서브 트리를 가질 필요는 없다.

 

3) 정 이진 트리 (full binary tree)

- 모든 노드가 0개 혹은 2개의 자식 노드를 가지는 트리.

3. Traversal

 

하나의 논리적인 흐름을 가지고 있는 선형 구조와는 달리 트리는 여러가지 순회 방법을 가지고 있다. 일반적으로 많이 사용되는 트리 순회 방법으로는 root, left, right 3개의 노드들을 방문하는 순서에 따라 구분되는 preorder, inorder, postorder 3가지 방법이 있다.

1) Preorder Traversal

전위 순회 방법은 root 노드를 먼저 방문 후 left, right 순으로 방문하는 방법이다.

 

function PreOrder(root):
	visit(root)
	PreOrder(root.left)
	PreOrder(root.right)

2) Inorder Traversal

중위 순회 방법은 left 노드를 방문 후 root, right 노드 순으로 방문한다.

 

function InOrder(root):
	InOrder(root.left)
	visit(root)
	InOrder(root.right)

3) Postorder Traversal

후위 순회 방법은 left 노드를 방문 후 right 노드를 먼저 방문하고 마지막에 root 노드를 방문한다.

 

function PostOrder(root):
	PostOrder(root.left)
	PostOrder(root.right)
	visit(root)

binary tree 자바 구현

public class CustomBinaryTree implements CustomTree {
    public class Node {
        int value;
        Node left;
        Node right;

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

    Node root;

    public CustomBinaryTree() {
        this.root = null;
    }

    @Override
    public boolean insert(int value) {
        Node newNode = new Node(null, value, null);
        if(this.root == null) {
            this.root = newNode;
            return true;
        }

        Node node = this.root;
        while(node != null) {
            if(node.value == value) {
                return false;
            } else if(node.value < value) {
                if(node.right == null) {
                    node.right = newNode;
                    break;
                }
                node = node.right;
            } else {
                if(node.left == null) {
                    node.left = newNode;
                    break;
                }
                node = node.left;
            }
        }
        return true;
    }

    private void replace(Node parent, Node node) {
        Node target = null;
        if(node.left == null) {
            target = node.right;
        } else if(node.right == null) {
            target = node.left;
        } else {
            // find min leaf of right subtree of node
            target = node.right;
            while(target.left != null) {
                target = target.left;
            }
        }

        if(parent.left == node) {
            parent.left = target;
        } else {
            parent.right = target;
        }
    }

    @Override
    public boolean remove(int value) {
        Node parentNode = null;
        Node node = this.root;
        while(node != null) {
            if(node.value == value) {
                if(parentNode == null) {
                    node = null;
                } else {
                    replace(parentNode, node);
                }
                return true;
            } else if(node.value < value) {
                parentNode = node;
                node = node.right;
            } else {
                parentNode = node;
                node = node.left;
            }
        }
        return false;
    }

    public void preOrder(Node node) {
        System.out.println(node.value);
        if(node.left != null) {
            preOrder(node.left);
        }
        if(node.right != null) {
            preOrder(node.right);
        }
    }

    @Override
    public void preOrder() {
        if(this.root != null) {
            System.out.println("pre");
            preOrder(this.root);
        }
    }

    public void inOrder(Node node) {
        if(node.left != null) {
            inOrder(node.left);
        }
        System.out.println(node.value);
        if(node.right != null) {
            inOrder(node.right);
        }
    }

    @Override
    public void inOrder() {
        if(this.root != null)
            inOrder(this.root);
    }

    public void postOrder(Node node) {
        if(node.left != null) {
            postOrder(node.left);
        }
        if(node.right != null) {
            postOrder(node.right);
        }
        System.out.println(node.value);
    }

    @Override
    public void postOrder() {
        if(this.root != null)
            postOrder(this.root); 
    }
    
}

4. Binary Search Tree

이진 탐색 트리는 효율적인 탐색을 위해 이진 트리에 특정한 규칙을 부여하여 구성한 트리를 말한다. 이진 탐색 트리에서의 탐색연산은 O(log N)의 시간 복잡도를 가진다.

 

이진 탐색 트리의 규칙은 다음과 같다.

- 이진 탐색 트리의 노드에 저장된 값은 유일하다.

- 부모 노드의 값이 왼쪽 자식 노드의 값보다 크다.

- 부모 노드의 값이 오른쪽 자식 노드의 값보다 작다.

- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리로 구성되어 있다.

 

이진 탐색 트리가 한쪽으로 노드들이 몰려있는 skewed tree인 경우가 worst case가 되는데, 이때는 O(N)의 시간 복잡도를 가지게 된다. 이를 해결하기 위해서 트리의 균형을 잡은 rebalancing 을 적용한 red black tree 와 같은 구조를 사용하기도 한다.

 

이진 검색

이진 탐색 트리를 통해서 원하는 값을 찾는 방법으로 노드의 값을 타겟 값과 비교하여 진행한다.

 

function BST(node, target):
	if(node == null):
    	return null

	if(node.val == target):
		return node
	else if(node.val < target):
		return BST(node.right, target)
	else if(target < node.val):
		return BST(node.left, target)

 

[reference]

- https://www.geeksforgeeks.org/binary-tree-data-structure/

- https://librewiki.net/wiki/시리즈:수학인듯_과학아닌_공학같은_컴퓨터과학/알고리즘_기초