[Tree 라이브러리 제작] (1) 이진탐색트리(Binary Search Tree) 구현

계획

주요 클래스

BSTreeNode

트리의 각 노드가 될 클래스

BSTree

BSTreeNode가 구조적으로 모여있는 트리클래스

기능

모든 기능에서 최대한 재귀호출을 지양하는 방식으로 구현

초기화

트리 구조로 구성된 일반 객체를 인자로 받아 BSTreeNode, BSTree 객체 초기화

삽입

새 노드를 어디에 삽입할지 다음의 과정을 따라 계산.

• ROOT 노드부터 시작하여 삽입할 key와 노드의 key를 비교해서, 해당 노드의 왼쪽자식 또는 오른쪽자식과 다시 비교
• 더이상 자식노드로 이동할 수 없을 때 해당 노드의 자식으로 새 노드 삽입

재귀호출을 피하기 위해 BSTreeNode 객체에 key 비교 + 왼쪽/오른쪽 자식으로 redirect 시키는 메서드를 두고,
해당 메서드를 반복적으로 호출하는 방식으로 구현.

순회

재귀호출 없이 스택과 반복문으로 전위(pre-order), 중위(in-order), 후위(post-order) 순회 구현

탐색

반복문 만으로 구현.

삭제

메서드 호출 시 전달한 옵션값에 따라 해당 노드만 삭제하거나 그 하위 모든 노드들도 삭제.

BSTreeNode 클래스 구현

클래스 구성

멤버 변수

• key: 노드의 대표값. 순회, 탐색, 삽입, 삭제 등의 모든 기능의 알고리즘에 사용된다.
• left: 자식 노드 (왼쪽)
• right: 자식 노드 (오른쪽)
• data: 노드에 포함시킬 커스텀 데이터

메서드

• redirect: 트리에 새로운 데이터 삽입 시, 어느 노드의 어느 방향 자식으로 추가할지 찾아가기 위한 메서드.
• getLeftLeaf: 노드 삭제 시, 그 자식 중 해당 노드의 위치를 대신할 새 노드를 찾기 위해 사용.
• getRightLeaf: 사용 계획은 없지만 getLeftLeaf 구현하는 김에 같이 구현해둔 메서드.

redirect() 구현

삽입할 key와 해당 노드의 key를 비교하여,
왼쪽/오른쪽 자식에게 다시 물어보라고 알려주거나
혹은 자기 자신의 왼쪽/오른쪽 자식으로 삽입하면 된다고 알려주는 역할

시그니처

redirect(newKey: number): {
  node: BSTreeNode<T>;
  direction: -1 | 0 | 1;
  redirect: boolean;
}

redirect
자신이 부모노드가 될 건지 혹은 자신의 자식노드에게 다시 물어봐야 하는지.

• true: 그 자식 노드에게 다시 redirect() 메서드를 호출하여 값을 비교
• false: 반복적인 redirect()를 멈추고 노드를 삽입함.

node

• redirect = true인 경우: 다음으로 물어볼 노드
• redirect = false인 경우: 새 노드의 부모가 될 노드

direction

• redirect = true인 경우: 'node는 자신의 왼쪽 자식이다'
• redirect = false인 경우: 'node의 왼쪽 자식으로 삽입하면 된다'를 의미

메서드 전체 코드

redirect(newKey) {
  // 중복 방지
  if (newKey === this.key)
    return {
      node: this,
      direction: 0,
      redirect: false,
    };

  // redirect to left
  if (newKey < this.key) {
    if (this.left === null)
      return {
        node: this,
        direction: -1,
        redirect: false,
      };

    return {
      node: this.left,
      direction: -1,
      redirect: true,
    };
  }

  // redirect to right
  if (newKey > this.key) {
    if (this.right === null)
      return {
        node: this,
        direction: 1,
        redirect: false,
      };

    return {
      node: this.right,
      direction: 1,
      redirect: true,
    };
  }
}

getLeftLeaf() 구현

시그니처

getLeftLeaf(node?: BSTreeNode<T>): BSTreeNode<T>

메서드 전체 코드

getLeftLeaf(node = this) {
  let currentNode = node;
  while (currentNode.left) {
    currentNode = currentNode.left;
  }
  return currentNode;
}

getRightLeaf() 메서드 전체 코드

getLeftLeaf()와 동일

getRightLeaf(node = this) {
  let currentNode = node;
  while (currentNode.right) {
    currentNode = currentNode.right;
  }
  return currentNode;
}

BSTree 클래스 구현

클래스 구성

멤버 변수

• root: 트리의 ROOT 노드

메서드

• insert: 삽입
• traverse: 순회
• search: 탐색
• deleteByKey: 삭제. 추후 조건에 해당하는 모든 노드를 삭제하는 기능을 만들고자 네이밍에 'ByKey'를 넣음.

insert() 구현

BSTreeNode.redirect() 메서드를 활용하여 삽입 지점을 찾고, 트리에 새 노드 추가.
삽입된 새 노드가 몇번째 depth인지 반환.

메서드 전체 코드

insert(newKey, data) {
  if (!this.root) {
    this.root = new BSTreeNode(newKey, data);
    return { depth: 0 };
  }

  let result = null;
  let currentNode = this.root;
  let depth = 0;
  while (true) {
    depth++;
    result = currentNode.redirect(newKey);
    currentNode = result.node;

    if (!result.redirect) {
      if (result.direction === 0) break;

      currentNode[result.direction === -1 ? "left" : "right"] =
        new BSTreeNode(newKey, data);
      break;
    }
  }

  return { depth };
}

traverse() 메서드 구현

전위/중위/후위 등 원하는 방향으로 순회 후, 순회한 key 배열을 응답

시그니처

traverse: (
  orderWay: TBSTreeTraverseOrderWay,
  cb?: (node: BSTreeNode<TData>) => void
) => BSTreeNode<TData>[];

orderWay
어느 방향으로 순회할지.

• pre: 전위(pre-order) 순회
• in: 중위(in-order) 순회 - 오름차순
• out: 중위(in-order) 순회 - 내림차순
• post: 후위(post-order) 순회

cb
순회하는 각 노드를 대상으로 실행시킬 콜백함수

메서드 전체 코드

각 순회방향별로 다른 방식으로 스택 자료구조와 반복문을 사용하여 순회

traverse(orderWay, cb) {
  if (!this.root) return [];

  const result = [];
  const stack = [];
  let currentNode = this.root;
  switch (orderWay) {
    case "pre":
      while (true) {
        if (!currentNode) {
          if (!stack.length) break;

          currentNode = stack.pop();
        }

        if (cb) cb(currentNode);
        result.push(currentNode.key);

        if (currentNode.right) stack.push(currentNode.right);
        currentNode = currentNode.left;
      }
      return result;
    case "in":
      while (true) {
        let isPopped = false;
        if (!currentNode) {
          if (!stack.length) break;

          currentNode = stack.pop();
          isPopped = true;
        }

        if (isPopped) {
          if (cb) cb(currentNode);
          result.push(currentNode.key);
          currentNode = currentNode.right;

          continue;
        }

        stack.push(currentNode);
        currentNode = currentNode.left;
      }

      return result;
    case "out":
      while (true) {
        let isPopped = false;
        if (!currentNode) {
          if (!stack.length) break;

          currentNode = stack.pop();
          isPopped = true;
        }

        if (isPopped) {
          if (cb) cb(currentNode);
          result.push(currentNode.key);
          currentNode = currentNode.left;

          continue;
        }

        stack.push(currentNode);
        currentNode = currentNode.right;
      }

      return result;
    case "post":
      const stackPost = [];
      while (true) {
        if (!currentNode) {
          if (!stackPost.length) break;

          const popped = stackPost.pop();
          currentNode = popped.node;

          if (popped.isHead) {
            if (cb) cb(currentNode);
            result.push(currentNode.key);
            currentNode = null;
            continue;
          }
        }

        stackPost.push({ node: currentNode, isHead: true });
        if (currentNode.right)
          stackPost.push({ node: currentNode.right, isHead: false });
        currentNode = currentNode.left;
      }

      return result;
    default:
      return [];
  }
}

search() 메서드 구현

시그니처

search: (key: number) => {
  node: BSTreeNode<TData> | null;
  parentNode: BSTreeNode<TData> | null;
  direction: -1 | 0 | 1 | null;
  depth: number;
};

• node: 검색된 노드. 찾지 못했을 경우 null.
• parentNode: 검색된 노드의 부모 노드. 찾지 못했을 경우, 마지막으로 도달한 노드.
• direction: node가 parentNode의 어느 방향 자식인지.
• depth: 검색된 노드의 depth. 찾지 못했을 경우 parentNode의 depth.

메서드 전체 코드

search(key) {
  if (!this.root) return null;

  let currentNode = this.root;
  let parentNode = null;
  let direction = null;
  let depth = 0;
  while (true) {
    if (currentNode.key === key)
      return { node: currentNode, parentNode, direction, depth };

    if (key < currentNode.key) {
      if (currentNode.left === null)
        return {
          node: null,
          parentNode: currentNode,
          direction: null,
          depth,
        };
      parentNode = currentNode;
      currentNode = currentNode.left;
      direction = -1;
      depth++;
    }

    if (key > currentNode.key) {
      if (currentNode.right === null)
        return {
          node: null,
          parentNode: currentNode,
          direction: null,
          depth,
        };
      parentNode = currentNode;
      currentNode = currentNode.right;
      direction = 1;
      depth++;
    }
  }
}

deleteByKey() 메서드 구현

시그니처

deleteByKey: (key: number, options?: { cascade?: boolean }) => boolean

cascade

• true: key에 해당하는 노드와 모든 자식노드를 지움
• false: key에 해당하는 노드 하나만 지움
  기본값: false

메서드 전체 코드

deleteByKey(key, options) {
  if (!this.root) return false;
  const found = this.search(key);
  if (!found.node) return false;

  const cascade = options?.cascade ?? false;

  found.parentNode[found.direction === -1 ? "left" : "right"] = null;
  if (cascade) return true;

  // not cascade
  found.parentNode[found.direction === -1 ? "left" : "right"] =
    found.node.right;
  found.node.right.getLeftLeaf().left = found.node.left;

  return true;
}

클래스 전체 코드

BSTreeNode

class BSTreeNode {
  constructor(key, data) {
    this.key = key;
    this.left = null;
    this.right = null;
    this.data = data ?? null;
  }

  redirect(newKey) {
    // 중복 방지
    if (newKey === this.key)
      return {
        node: this,
        direction: 0,
        redirect: false,
      };

    // redirect to left
    if (newKey < this.key) {
      if (this.left === null)
        return {
          node: this,
          direction: -1,
          redirect: false,
        };

      return {
        node: this.left,
        direction: -1,
        redirect: true,
      };
    }

    // redirect to right
    if (newKey > this.key) {
      if (this.right === null)
        return {
          node: this,
          direction: 1,
          redirect: false,
        };

      return {
        node: this.right,
        direction: 1,
        redirect: true,
      };
    }
  }

  getLeftLeaf(node = this) {
    let currentNode = node;
    while (currentNode.left) {
      currentNode = currentNode.left;
    }
    return currentNode;
  }

  getRightLeaf(node = this) {
    let currentNode = node;
    while (currentNode.right) {
      currentNode = currentNode.right;
    }
    return currentNode;
  }
}

BSTree

class BSTree {
  constructor(initialData) {
    this.root = null;

    if (!initialData) return;

    this.root = this.initialize(initialData);
  }

  initialize(initialData) {
    const node = new BSTreeNode(initialData.key, initialData.data);
    if (initialData.left) node.left = this.initialize(initialData.left);
    if (initialData.right) node.right = this.initialize(initialData.right);

    return node;
  }

  insert(newKey, data) {
    if (!this.root) {
      this.root = new BSTreeNode(newKey, data);
      return { depth: 0 };
    }

    let result = null;
    let currentNode = this.root;
    let depth = 0;
    while (true) {
      depth++;
      result = currentNode.redirect(newKey);
      currentNode = result.node;

      if (!result.redirect) {
        if (result.direction === 0) break;

        currentNode[result.direction === -1 ? "left" : "right"] =
          new BSTreeNode(newKey, data);
        break;
      }
    }

    return { depth };
  }

  traverse(orderWay, cb) {
    if (!this.root) return [];

    const result = [];
    const stack = [];
    let currentNode = this.root;
    switch (orderWay) {
      case "pre":
        while (true) {
          if (!currentNode) {
            if (!stack.length) break;

            currentNode = stack.pop();
          }

          if (cb) cb(currentNode);
          result.push(currentNode.key);

          if (currentNode.right) stack.push(currentNode.right);
          currentNode = currentNode.left;
        }
        return result;
      case "in":
        while (true) {
          let isPopped = false;
          if (!currentNode) {
            if (!stack.length) break;

            currentNode = stack.pop();
            isPopped = true;
          }

          if (isPopped) {
            if (cb) cb(currentNode);
            result.push(currentNode.key);
            currentNode = currentNode.right;

            continue;
          }

          stack.push(currentNode);
          currentNode = currentNode.left;
        }

        return result;
      case "out":
        while (true) {
          let isPopped = false;
          if (!currentNode) {
            if (!stack.length) break;

            currentNode = stack.pop();
            isPopped = true;
          }

          if (isPopped) {
            if (cb) cb(currentNode);
            result.push(currentNode.key);
            currentNode = currentNode.left;

            continue;
          }

          stack.push(currentNode);
          currentNode = currentNode.right;
        }

        return result;
      case "post":
        const stackPost = [];
        while (true) {
          if (!currentNode) {
            if (!stackPost.length) break;

            const popped = stackPost.pop();
            currentNode = popped.node;

            if (popped.isHead) {
              if (cb) cb(currentNode);
              result.push(currentNode.key);
              currentNode = null;
              continue;
            }
          }

          stackPost.push({ node: currentNode, isHead: true });
          if (currentNode.right)
            stackPost.push({ node: currentNode.right, isHead: false });
          currentNode = currentNode.left;
        }

        return result;
      default:
        return [];
    }
  }

  search(key) {
    if (!this.root) return null;

    let currentNode = this.root;
    let parentNode = null;
    let direction = null;
    let depth = 0;
    while (true) {
      if (currentNode.key === key)
        return { node: currentNode, parentNode, direction, depth };

      if (key < currentNode.key) {
        if (currentNode.left === null)
          return {
            node: null,
            parentNode: currentNode,
            direction: null,
            depth,
          };
        parentNode = currentNode;
        currentNode = currentNode.left;
        direction = -1;
        depth++;
      }

      if (key > currentNode.key) {
        if (currentNode.right === null)
          return {
            node: null,
            parentNode: currentNode,
            direction: null,
            depth,
          };
        parentNode = currentNode;
        currentNode = currentNode.right;
        direction = 1;
        depth++;
      }
    }
  }

  deleteByKey(key, options) {
    if (!this.root) return false;
    const found = this.search(key);
    if (!found.node) return false;

    const cascade = options?.cascade ?? false;

    found.parentNode[found.direction === -1 ? "left" : "right"] = null;
    if (cascade) return true;

    // not cascade
    found.parentNode[found.direction === -1 ? "left" : "right"] =
      found.node.right;
    found.node.right.getLeftLeaf().left = found.node.left;

    return true;
  }
}