(JS 알고리즘) 이진탐색트리(Binary Search Tree)

트리(Tree)

트리란?

• 트리는 parent , child 관계를 지닌 노드들로 구성된 자료구조다.

• 리스트는 일렬로 쭉 이어지는 선형(linear) 구조인 반면에, 트리는 여러 갈래로 뻗을 수 있는 비선형(nonlinear) 구조이다.

• 트리에서 노드는 부모-자식 관계에 따라 자식인 노드만을 가리킬 수 있다. 부모나 형제를 가리키는 노드가 있어서는 안 된다. 또한 출발점(루트)는 하나여야 한다.

트리 용어 정리

• Root : 트리의 최상위 노드(하나만 존재)
• Siblings : 부모가 동일한 노드 그룹(여러개가 존재할 수 있음 - 형제)
• Leaf : 하위에 Child가 없는 노드
• Edge(간선) : 한 노드와 다른 노드 간의 연결
• 트리 사용 ex) HTML,DOM, NETWORK ROUTING,운영체제 폴더 방식

이진 탐색 트리

• 이진 트리(Binary Tree)는 트리의 일종이다.
• 이진 트리는 각 노드가 최대 두 개의 자식을 가져야한다는 규칙이 있다. 따라서 각 노드의 자식이 0개거나 1개거나 2개일 수 있다. 이러한 이진 트리의 구조는 순회가 쉽다는 강점이 있다.
• 이진 탐색 트리는 이진 트리의 특별한 종류이다. 용어 그대로 이진 트리 중에서 탐색에 더욱 강점이 있는 자료구조다.
  • 모든 부모 노드는 최대 두 자식 노드를 갖는다.
  • 부모 노드의 왼쪽에 있는 모든 노드는 항상 부모보다 작다.
  • 부모 노드보다 오른쪽에 있는 모든 노드는 언제나 부모보다 크다.

기본 구조

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

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

insert 메소드

insert(value){
        let insertval = new Node(value);
  		//root가 없을 시 새 노드가 루트가 되고 반환
        if(!this.root === null){
            this.root = insertval;
            return this;
        }else{
          //root가 있으면 root부터 아래로 순회하며 값이 들어갈 곳을 찾음
            let current = this.root;
            while(true){
                if(value === current.value) return undefined;
              //삽입할 값이 현재 루트보다 작고 그 왼쪽이 비어있으면
                if(current.value > value){
                    if(current.left === null){
                        current.left = insertval;
                        return this;
                    }
                  //비어있지 않으므로 그 왼쪽을 변수에 넣어 그 child 순회를 진행
                    current = current.left;
                }
              //삽입할 값이 현재 루트보다 크고 오른쪽이 비어있으면
                else if(current.value < value){
                    if(current.right === null){
                        current.right = insertval;
                        return this;
                    }
                  //비어있지 않으므로 오른쪽을 변수에 넣어 그 child 순회를 진행
                    current = current.right;
                } 
            }
        } 
    }

Find 메소드

find(value){
        //루트가 없으면 false 반환
        if(this.root === null) return false;
        let current1 = this.root;
        let found = false;

        while(current1 && !found){
          //찾는 값이 현재 루트보다 작으면 왼쪽 순회
            if(value < current1.value){
                current1 = current1.left
              //찾는 값이 현재 루트보다 크면 오른쪽 순회
            }else if(value > current1.value){
                current1 = current1.right;
              //둘 다 아니면 찾는값임
            }else{
                return true;
            }
        }
        return false;
    }

이진탐색트리(BST)의 성능

• 삽입 : O(logn)
• 탐색 : O(logn)
• 이진탐색트리는 특정하게 데이터가 정렬되어져있으므로 삽입과 탐색에서 빠르다.
• 데이터가 한쪽으로 치우쳐 있을 경우 최악의 상황으로 O(n)의 시간복잡도를 가질 수 있어서 이럴 경우에는 연결리스트 같은 다른 자료구조를 사용하는게 좋다.