Section22 - 이진 검색 트리

---

---

[트리]

 

트리는 연결리스트 보다 약간 더 상위 단계고 복잡함

한 개의 노드는 여러개를 가질 수 있음

 

List - linear

Trees - nonlinear

 

부모자식 구조로 이루어져있지 않으면 트리가 아님

 

Root - 트리의 탑 노드

Child - 다른 노드와 직접적으로 연결되어 있는 노드, 루트로부터 멀어짐

Parent - 자식의 반대

Siblings - 같은 부모 그룹의 노드

Leaf - Child가 없는 노드

Edge - 간선

 

Ex)

- HTML DOM

- Network Routing

- 추상 구문 트리

- 인공 지능

- 폴더 설계 방식

- JSON

 

[트리의 종류]

- 트리

- 2진 트리

- 2진 검색 트리(BST)

 

[이진 검색 트리]

 

class Node {
  constructor(val){
    this.val = val;
    this.left = null;
    this.rigth = null;
  }
}

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

  insert(val){

    const newNode = new Node(val);

    if(this.root === null){
      this.root = newNode;
      return this;
    } else {
      let current = this.root;

      if(current.val === val) return undefined;

      while(true){
        if(val < current.val){
          if(current.left === null){
            current.left = newNode;
            return this;
          } else {
            current = current.left;
          }
        } else if (val > current.val){
          if(current.right === null){
            current.right = newNode;
            return this;
          } else {
            current = current.right;
          }
        }
      }
    }
  }

  contains(val){

    if(this.root === null) return false;
    
    let current = this.root;
    let found = false;

    while(current && !found){

      

      if(val < current.val){
        current = current.left;
      } else if (val > current.val) {
        current = current.rigth;
      } else {
        return true;
      }

    }
    return false;
  }

}

 

 

[이진 검색 트리 BIG O]

 

삽입 - O(logN)

검색 - O(logN)

 

not guaranteed

(만약 싱글 연결리스트 따위의 구조라면?)