[자료구조] 이진탐색트리

HYEJIN·2023년 1월 26일

알고리즘

목록 보기

5/6

트리

부모와 자식간의 관계로 구성되어 있다.
리스트는 선형구조 ( 한줄로 있는 구조 )
트리는 비선형 구조 ( 한 갈래에서 여러가지 가지로 뻗어나갈 수 있다 )

트리는 부모-자식 관계에 따라서 자식 노드만 가리킬 수 있다.
자식이 부모를 가리키거나 형제를 가리킬 수 없다 >> 이것은 그래프다.

용어

루트 - 트리의 최상위 노드 (꼭대기)
자식 - 루트로부터 하위로 연결된 노드
부모 - 현재 노드에 상위로 연결된 노드
형제 - 같은 부모를 가지는 노드
리프 - 자식이 없는 노드 (끝)
간선(edge) - 한 노드에서 다른 노드로 연결하는 선

트리의 사용 예시

HTML DOM - HTML 요소인 문자들 사이의 관계는 부모 자식 관계
JSON
프로로그래밍 구문 구조
네트워크 라우팅
인공지능
운영체제에서의 폴더구조 ( 폴더 안의 파일 )

이진트리

일반적인 트리는 자식이 몇개 있던 상관없지만 이진트리의 경우는 각 노드가 최대 두개의 자식을 가져야한다.

이진탐색트리 (BST)

이진 트리의 종류로, 최대 2개의 자식
데이터 순서에 따라 정렬되어 있다.
- 특정 노드의 왼쪽은 그 노드보다 작은 값, 오른쪽 노드는 큰 값

왜 사용할까 ?

작은 것들은 왼쪽, 큰 것들은 오른쪽에 놓는 방식이 어떠한 값을 찾는데에 빠르게 동작한다.
정렬되지 않은 트리와 비교했을 때는 어떠한 값을 찾는다면 이진탐색트리가 더 유리하다.
일반트리에서는 모든 값들을 순회해야하지마 BST에서는 비교할 때마다 탐색해아하는 횟수나 노드의 숫자가 줄어든다 .

BST 구현

기본구조

class BinarySearchTree{
      constructor(){
          this.root = null;
      }
  }
  
  class Node{
      constructor(value){
          this.value = value;
          this.left = null;
          this.right= null;
      }
  }
  
  let 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 메서드

의사코드

넣어줄 생성할 노드를 만든다.
루트에서 시작한다
- 루트가 없을 경우, 현재값이 루트가 된다.
- 루트가 있을 경우, 값이 큰지 작은지 비교한다.
  - 값이 클 경우
    - 오른쪽에 자식노드가 있는지 체크한다.
      - 자식노드가 있다면 그곳과 비교를 반복한다.
      - 자식 노드가 없다면 오른쪽에 추가한다.
  - 값이 작은 경우
    - 왼쪽에 자식노드가 있는지 체크한다.
      - 자식 노드가 있다면 그곳과 비교를 반복
      - 자식 노드가 없다면 왼쪽에 추가.

코드

insert(value){
        let newNode = new Node(value);

        if(!this.root){ 
            this.root = newNode;
            return this 
        }
        
        let curNode = this.root;
        let count=0;
        while(curNode){
            if(value === curNode.value) return undefiend;
            if(value < curNode.value) {
                if(curNode.left === null) {
                    curNode.left = newNode;
                    return this;
                }
                curNode = curNode.left
            }
            else {
                if(curNode.right === null) {
                    curNode.right = newNode;
                    return this;
                }
                curNode = curNode.right
            }
        }
        return this;
    }

### contains메서드 insert와 값을 비교하는 것은 똑같지만, 만약 현재 노드가 null일 경우는 값을 찾지 못했음을 의미하므로 중단한다. **코드**

find(value){
        if(!this.root) return false;

        let curNode = this.root;
        while(curNode){

            if(curNode.value===value) return true;

            if(value<curNode.value) curNode= curNode.left;
            else curNode = curNode.right;
            
        }
        return false
    }