트리 소개

트리란 고전적인 데이터 구조를 말합니다.
연결 리스트처럼 노드로 이루어졌습니다. 노드들 사이에서 부모 자식 관계를 가지며, 한개의 부모 밑에는 여러가지의 자식 노드를 가질 수 있습니다.

리스트는 하나의 라인으로 구성되어있습니다. 즉 하나의 경로 밖에 없습니다.
하지만 트리 같은 경우 선형적이지 않고, 여러개의 갈래로 나눠 질 수 있습니다. 즉 경로에 여러가지 경우의 수가 만들어 질 수 있습니다.

위의 두 그림은 트리라고 할 수 없습니다. 트리구조에는 부모 자식의 관계만 가져야합니다. 형제 관계는 없습니다. 또한 오직 하나의 루트만 가져야 한다는 것, 자식노드가 부모노드를 가르킬 수 는 없다는 것 등을 유의해야합니다.

• Root : 최상단 노드
• Child : 다른 노드랑 연결되어있고, Root에서 멀어지는 방향의 노드
• Parent : 위의 자식노드의 반대
• Siblings : 같은 부모노드를 가진 자식노드들
• Leaf : 자식노드를 갖고 있지 않은 노드, 최하단 노드
• Edge : 노드와 노드를 연결해주는 선

트리 사용

대표적인 예는 HTML DOM 입니다.
정확하게 트리구조를 갖고 있고, 자바스크립트로 이를 동적으로 가져갈 수 있습니다.
네트워크 라우팅을 할 때도 트리구조를 이용해서 라우팅을 해주고, 추상화와 같은 다양한 분야에 트리 구조가 응용 됩니다.

이진 트리 소개

트리 중에서 이진 트리! (binary tree)

트리에는 매우 다양한 종류가 있습니다. 그 중 가장 대표적인 이진 트리에 대해 알아보겠습니다.
이진 트리란 : 일반적인 트리구조에서 하나의 법칙을 추가합니다. 그 법칙은 하나의 노드가 가질수 있는 최대 자식노드가 2개라는 것 입니다.
(최대 이기 때문에 가질 수 있는 자식노드의 수는 0,1,2 3가지 경우의 수를 갖습니다)

이진 검색 트리

위의 그림은 이진 검색 트리 입니다. 루트 노드가 8이죠. 이 값보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 배치를 합니다. 루트의 자식노드 3과 10에서도 마찬가지로 작은 값은 왼쪽, 큰 값을 오른쪽에 배치하면서 검색을 진행하는 구조입니다.

위의 그림에 나오는 각 노드를 수평선에 배치하면 크기에 맞게 정렬된 상태인 것을 확인할 수 있습니다. 정렬된 배열에서 사용하며, 검색 속도가 빠르다는 것이 장점입니다.

왜 이것을 사용하나요?

빠르다는 것입니다. 하나씩 다 확인하지 않아도 원하는 값을 찾을 수 잇죠.

트리 클래스

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
}

var tree = new BinarySearchTree();
tree.root = new Node(10);
tree.root.right = new Node(15);
tree.root.left = new Node(7);
tree.root.left.right = new Node(9);

이진 검색 트리 메소드

Insert 메소드

이진트리에 값을 삽입하는 메소드에 대해 알아 보겠습니다.
1. root 에 있는 노드와 값을 비교합니다. 그보다 크면 오른쪽 작으면 왼쪽으로 이동합니다.
2. 1번과 마찬가지로 비교 후 그에 맞게 이동합니다.
3. 위의 과정을 더 이상 비교할 필요가 없을때 (Leaf와 비교가 마지막 비교)까지 비교합니다.

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }
}


//      10
//   5     13
// 2  7  11  16

var tree = new BinarySearchTree();
tree.insert(10)
tree.insert(5)
tree.insert(13)
tree.insert(11)
tree.insert(2)
tree.insert(16)
tree.insert(7)

Find 메소드

사실 find 즉 이진트리에서 특정 값을 찾는 방식은 insertion과 매우 유사합니다.
기본적으로 같은 방식으로 값을 찾아나가기 때문입니다.

마지막 Leaf와 비교해서 없을 경우, false 를 반환하는 것이 특징 입니다.

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }
    find(value){
        if(this.root === null) return false;
        var current = this.root,
            found = false;
        while(current && !found){
            if(value < current.value){
                current = current.left;
            } else if(value > current.value){
                current = current.right;
            } else {
                found = true;
            }
        }
        if(!found) return undefined;
        return current;
    }
    contains(value){
        if(this.root === null) return false;
        var current = this.root,
            found = false;
        while(current && !found){
            if(value < current.value){
                current = current.left;
            } else if(value > current.value){
                current = current.right;
            } else {
                return true;
            }
        }
        return false;
    }
}


//      10
//   5     13
// 2  7  11  16

var tree = new BinarySearchTree();
tree.insert(10)
tree.insert(5)
tree.insert(13)
tree.insert(11)
tree.insert(2)
tree.insert(16)
tree.insert(7)

이진 검색 트리 빅오

• Insertion : O(log n)
• Searching : O(log n)

Not guaranteed