인프런 커뮤니티 질문&답변

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

class BinarySearchTree {
  constructor() {
    this.root = null;
    // 숙제 몇개 인지 확인하는 count
    this.length = 0;
  }

  #insert(node, value) {
    if (node.value > value) {
      // 루트노드보다 작은 값이면
      if (node.left) {
        this.#insert(node.left, value);
      } else {
        node.left = new Node(value);
      }
    } else {
      // 숙제 : 같은 값을 넣은경우 에러 처리 (alert, throw)
      if (node.value === value)
        throw new Error(`이미 해당 ${value}가 존재 합니다`);
      // 루트노드보다 큰 값이면
      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);
    }
    this.length++;
  }

  #search(node, value) {
    if (!node) return null;

    if (node.value > value) {
      return this.#search(node.left, value);
    } else if (node.value === value) {
      return node;
    } else {
      return this.#search(node.right, 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) {
    if (!this.root) return null;

    if (this.root.value === value) {
      return this.root;
    }
    return this.#search(this.root, value);
  }

  #remove(node, value) {
    if (!node) {
      // 제거 할 값이 bst에 존재하지 않는 경우
      return null; // 지울 값이 존재 안하면 null return
    }

    if (node.value === value) {
      // 자식 입장
      // 지울 값을 찾은 경우
      if (!node.left && !node.right) {
        this.length--;
        // leaf
        return null;
      } else if (!node.left) {
        // 왼팔만 없는 경우
        return node.right; // 왼팔이 없는 경우 자기 왼팔 대신 오른팔을 쓰라고 return 해줌
      } else if (!node.right) {
        // 오른팔만 없는 경우
        return node.left; // 오른팔 없는 경우 자기 오른팔 대신 왼팔을 쓰라고 return 해줌
      } else {
        // 양팔 다 있는 경우
        let exchange = node.left;
        while (exchange.right) {
          exchange = exchange.right;
        }
        const temp = node.value;
        node.value = exchange.value;
        exchange.value = temp;
        node.left = this.#remove(node.left, exchange.value);
        return node;
      }
    } else {
      // 부모 입장
      if (node.value > value) {
        node.left = this.#remove(node.left, value);
        return node;
      } else {
        node.right = this.#remove(node.right, value);
        return node;
      }
    }
  }

  remove(value) {
    // 1. leaf(양팔 다 없음) -> 제거
    // 2. leaf x, 왼팔이 없다 -> 오른팔 끌어올린다
    // 3. leaf x, 오른팔이 없다 -> 왼팔 끌어올린다
    // 4. leaf x, 양팔 다 있다 -> 왼팔에서 가장 큰 애와 바꾼다, leaf를 지운다
    this.root = this.#remove(this.root, value);

    // return 숙제 length return 하기
    return this.length;
  }
}

const bst = new BinarySearchTree();

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.length); // 9
console.log(bst.remove(8)); // 8
bst.search(7);
bst.search(5);
console.log(bst.remove(4)); // 7
console.log(bst.remove(15)); // 없는 값을 지운다면 현재 length return 7

숙제 정답일까요?

제발 ㅠㅠ 🙏