• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

숙제 length return 하기

24.06.14 17:41 작성 조회수 64

0

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

숙제 정답일까요?

제발 ㅠㅠ 🙏

답변 1

답변을 작성해보세요.

0

인프런 AI 인턴님의 프로필

인프런 AI 인턴

2024.06.16

안녕하세요, 인프런 AI 인턴입니다.

제공해주신 코드를 확인해본 결과, 기본적인 이진 탐색 트리(Binary Search Tree, BST)의 구현과 함께, 노드의 삽입(insert), 삭제(remove), 검색(search) 기능을 제공하며, 노드를 삭제할 때마다 트리의 길이(length)를 갱신하는 부분을 포함하고 있습니다.

노드의 삽입 과정에서 동일한 값을 가진 노드의 중복 삽입을 방지하려는 예외 처리가 들어가 있고, 삭제 과정에서는 리프 노드 삭제, 단일 자식 노드 삭제, 두 자식 노드를 가진 노드의 삭제 시 후속 처리를 적절하게 구현하였습니다. 또한, 삭제 연산 후 현재 트리 내의 노드 개수(length)를 반환하는 방식으로 구현되어 있습니다.

단, 이진 탐색 트리에서 노드 삭제 로직 중에, 양팔(두 자식 노드)을 모두 가진 노드를 삭제하는 경우, 해당 노드를 삭제하고 그 자리를 대체할 노드를 찾는 과정에서, 보통 삭제할 노드의 오른쪽 서브 트리에서 가장 작은 노드를 찾거나 왼쪽 서브 트리에서 가장 큰 노드를 찾아서 대체하는 방식을 사용합니다. 제공된 코드에서는 왼쪽 서브 트리에서 가장 큰 노드로 대체하는 로직을 사용하였는데, 이 과정에서 대체되는 노드의 값으로 기존 노드의 값을 교체한 후, 대체된 노드를 삭제하는 방식으로 잘 구현되어 있습니다.

따라서, 코드는 주어진 요구 사항을 만족하는 것으로 보이며, BST에 대한 기본적인 조작을 정확히 수행할 수 있는 구현으로 판단됩니다.

rhkdtjd_12님의 숙제에 대한 질문인 것으로 보이는데, 예, 잘 해결하신 것 같습니다! 🎉

도움이 필요하신 다른 부분이 있으면 언제든지 문의해주세요.

채널톡 아이콘