1. 이진트리 개념

최대 자식 2개

---

이진트리 종류

Full, Perfect, Complete, Degenereate, Balanced

(1) Full

모든 자식 개수가 0 또는 2

(2) Perfect (삼각형 구조)

• Leaf(=자식 0개인 노드)가 아닌 모든 노드의 자식이 2개
• Leaf가 다 같은 Level 이어야 함

(3) Complete (왼쪽부터)

• 왼쪽부터 데이터 차곡차곡 쌓아가면서 나오는 과정 중의 모든 트리구조
• Full 과 Perfect의 중간
• 언제 ? 데이터를 순서대로 하나씩 넣을 때 정해진 모양으로 넣을 수 있음
• 왜 ? Complete 트리 모양대로 넣으면 무조건 다음 위치가 정해져 있잖아!

(4) Degenerate (유사 LinkedList)

• 자식 개수 모두 1개
• 시간복잡도 O(n), 사실상 LinkedList와 다를 바 없는 비효율적인 이진 트리(이진트리라고 부르기도 뭐함)

(5) Balanced (균형)

• 모든 노드의 Diff가 0 또는 1개.
• Diff = 자기 기준으로 왼쪽 최대 Height & 오른쪽 최대 Height 차이
• 언제 ? 왼쪽 오른쪽 서로 치우쳐지지 않을 때

---

결론

가장 좋은 구조는 Balanced Tree

Perfect, Complete 는 무조건 Balanced이고, Full는 보장 X

cf) Balanced가 보장되는 자료구조 ⇒ AVL Tree, R/B Tree

---

이진탐색트리

노드를 기준으로 노드보다 작은 값이 왼쪽, 큰 값이 오른쪽으로 미리 배치되어 있음

탐색 = 이미 정렬되어 있다는 의미로 받아들이자

이미 정렬(탐색)이 되어 있으므로 (Balanced 가 항상 보장될 시) 조회, 삭제, 삽입 시 시간복잡도 O(logn)

O(logn)을 보장해주려면 AVL, R/B 작업을 해주면 됨

ex) 밸런스는 아니지만 이진 탐색 트리..

사실상 연결리스트 ⇒ O(n)

---

2. 구현하기

재귀함수, 전체와 부분이 똑같은 알고리즘 사용할 때

수정 없는 이유 = search 활용해서 값 변경하면 됨
ex. search(value, newValue){}

(1) insert 구현

class BinarySearchTree {
  root = null;

  // 재귀함수 사용 => subtree에게 insert 행동 위임한다는 것
  #insert(node, value){
    if(node.value > value){
      // 루트 노드보다 작은 값이면 왼쪽
      if(node.left){
        this.#insert(node.left, value);
      } else {
        node.left = new Node(value);
      }
    } else {
      // 루트 노드보다 큰 값이면 오른쪽
      if(node.right){
        this.#insert(node.right, value);
      } else {
        node.right = new Node(value);
      }
    }
  }

  insert(value){
    // 어떤 값을 넣으려 할 때, 일단 어디에 넣을지 모르겠다
    // 그래서 왼팔, 오른팔한테 맡긴다
    // 만약 왼팔 오른팔 없으면 거기다가 넣는다
    if(!this.root){
      this.root = new Node(value);
    } else {
      this.#insert(this.root, value);
    }

    /* 재귀 풀이 (위는 간결 ver.)

      if(this.root.value > value){
        // 루트 노드보다 작은 값이면 왼쪽
        this.#insert(this.root.left, value);
      } else {
        // 루트 노드보다 큰 값이면 오른쪽
        this.#insert(this.root.right, value);
      } */


    /* 재귀 사용 X
    
      if(this.root.value > value){
        this.root.left.insert(value);
      } else {
        this.root.right.insert(value);
      } */
	}
}

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

const bst = new BinarySearchTree();
// 8. 10, 3, 1, 14, 6, 7, 4, 13

---

(2) search 구현

class BinarySearchTree {
  root = null;
	
  #search(node, value){
    if(node.value > value){
      // 더 작은 값 찾을 때
      if(!node.left){
        return null;
      }
      if(node.left.value === value){
        return node.left;
      }
      return this.#search(node.left, value);
  
    } else {
      // 더 큰 값 찾을 떄
      if(!node.right){
        return null;
      }
      if(node.right.value === value){
        return node.right;
      } 
       return this.#search(node.right, value);
    }
  }
  search(value){
    // 어떤 값을 넣으려 할 때, 일단 어디에 있는지 모르겠다
    // 그래서 왼팔, 오른팔한테 맡긴다
    // 찾으면 그 노드 return, 못 찾으면 null return
    if(!this.root){
      // 예외 처리 중요, 초기값!초기값!초기값!
      return null;
    }
    if(this.root.value === value){
      return this.root;
    }
    return this.#search(this.root, value);
    
  }
  remove(value){

  }
  // update 없는 이유 = search 활용해서 값변경 
  // ex. search(value, newValue){}
}

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

---

(3) remove 구현

4가지 경우의 수
(1) leaf(양팔 다 ❌) => 제거
(2) leaf ❌ , 왼팔 없다 => 오른팔 끌어올림
(3) leaf ❌, 오른팔 없다 => 왼팔 끌어올림
(4) leaf ❌, 양팔 다 있다 => 왼팔에서 가장 큰 애와 바꾼다

📌 4번의 경우

class BinarySearchTree {
  root = null;
  #remove(node, value){
    if(!node){
      // 제거할 값이 BST에 존재하지 않을 때
      return false; // 지울 값이 없으면 false return 
    }
    if(node.value === value){ // 자식 입장
      // 지울 값을 찾은 경우
      if(!node.left && !node.right){ // leaf = 양팔이 없는 경우
          return null;
      } else if(!node.left){ // 왼팔만 없는 경우
          return node.right;
      } else if(!node.right){ // 오른팔만 없는 경우
          return node.left;
      } else { // 양팔 다 있는 경우
          let exchange = node.left; // node.left.right.right.right... left 한 번 이후, 최대한 오른쪽으로 가야함
          while(exchange.right){ // 가장 right값 탐색
            exchange = exchange.right;
          }
          let temp = node.value; // 값 변경
          node.value = exchange.value;
          exchange.value = temp;
          node.left = this.#remove(node.left, exchange.value); // 8이라는 값 제거
          return node;
      }
    } else { // (위임한) 부모 입장, 부모의 왼팔/오른팔, 자식의 값들이 합쳐지는 것
        if(node.value > value){
          node.left = this.#remove(node.left, value); // 자식이 null 리턴시 잘라버린다
          return node; // 대입할 값 return을 통해 update
        } else {
          node.right = this.#remove(node.right, value); // 자식이 null 리턴시 잘라버린다
          return node; // 대입할 값 return을 통해 update
        }
    }
  }
  remove(value){ 
    let node = this.#remove(this.root, value);
    if(node){ // 값을 못 찾은 경우 대비
      this.root = node; // 값을 찾은 경우에만 노드에 값 넣어주기
    }
  }
}

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

⭐️ remove 흐름 정리

실행 결과

const bst = new BinarySearchTree();
// 8. 10, 3, 1, 14, 6, 7, 4, 13
bst.insert(8);
bst.insert(10);
bst.insert(3);
bst.insert(1);
bst.insert(14);
bst.insert(6);
bst.insert(7);
bst.insert(4);
bst.insert(13);

console.log(bst.search(7)); // Node { left: null, right: null, value: 7 } 
console.log(bst.search(5)); // null
bst.remove(8);

---

console.log(bst.remove(15));// false가 맞지만,재귀라서 root 리턴 (나중에 수정하자)
bst.remove(4);
bst;

---

const bst2 = new BinarySearchTree();
bst2.insert(50);
bst2.remove(50); 
bst2.root; // nul