이진 탐색 트리(Binary Search Trees)

트리란?

연결 리스크처럼 노드로 이루어진 데이터 구조

A data structure that consists of nodes in a parent / child relationship. === branshing structure

➡ non-Linear 비선형구조이다.

• 자식이 부모 노드를 가리키거나, 형제를 가리키는 노드가 있으면 안 된다.
• 모든 노드가 루트에서 멀어지는 방식으로 연결된다. 모든 가지가 아래를 향하고 있다.

Root: the top node in a tree.
Child: A node directly connected to another node. when moving away from Root.
Parent: The converse notion of a child.
Siblings: A group of nodes with the same parent.
Leaf: A node with no children.
Edge: The connection between one node and another.

ex) HTML DOM, Network Routing, Abstract Syntax Tree, Artificial Intelligence, Floder in Operating Systems

 

이진 탐색

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다.

매우 넓은 탐색 범위에서 특정한 값을 구하거나, 정렬된 데이터에서 다수의 쿼리(query)를 날려야 하는 경우에 효과적으로 이용할 수 있다.

 

이진 탐색 트리

• 이진 트리의 특별한 종류이다.
• 모든 부모 노드는 최대 2개의 자식을 가진다.
• 부모 노드 기준, 왼쪽에 있는 노드는 언제나 부모보다 작고 오른쪽에 있는 노드는 언제나 부모보다 크다.

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;
    }
}

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)

insert 메소드

루트 노드가 있는지 확인한다. 새 노드 값이 루트 노드보다 크다면 오른쪽 값이 있는지 확인 후, 있다면 해당 노드로 이동하여 다시 비교한다. 만약 값이 없다면 그 곳에 값을 저장한다. 왼쪽도 이와 같은 방식으로 코드를 작성하면 된다. → while loof

 

find 메소드

루트가 있는지 확인한다. 새 노드 값과 루트 노드와 같은지 확인하여 크다면 오른쪽 값을 확인하고, 작다면 왼쪽 값을 확인하다. 값이 있다면 넘어가서 다시 과정을 반복한다. 없다면 그자리에서 끝이다.

 

contains 메소드

포함 여부를 boolean 값으로 반환한다.

 

이진 탐색 트리의 빅오

Insertion(삽입) ➡ O(log n)

Searching() ➡ O(log n)