[Data Structure & Algorithm] 이진 탐색 트리(BST) 개념과 구현

yoon·2023년 9월 28일
data structure프로그래머스 데브코스
0

프로그래머스 데브코스

목록 보기
5/15
post-thumbnail

트리

트리는 방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조이다. 따라서 정점이 N개인 트리는 반드시 N - 1개의 간선을 가진다. 계층구조를 추상화한 모델로 회사 조직이나 가계도 등이 트리 구조이다. 즉 부모-자식 관계를 가졌으며 최상위 노드를 제외하고 각 노드는 부모 노드를 갖는다.

최상위 노드를 루트(root)라고 하며 부모가 없는 노드이다. 자식이 없는 최하위 노드를 리프 노드(leaf node)라고 한다. 위에서 아래로 내려가는 계층 구조를 띄고 있기 때문에 루트 노드로부터 최하위 노드까지의 깊이를 나타낼 때 레벨(level) 혹은 높이라고 한다. 또한 한 노드와 다른 노드간에 연결되어 있는 간선들의 개수를 차수(degree)라고 한다.

이진 트리

이진트리는 노드는 좌, 우측에 각각 하나씩, 최대 2개의 자식 노드를 갖는 트리이다. 이진트리는 이진 탐색 트리, 힙 등에 사용된다. 이진 탐색 트리는 이진 트리의 변형으로, 좌측 노드에는 더 작은 값을, 우측 노드에는 더 큰 값을 들고 있다는 차이점이 있다. 이진트리는 연결리스트 혹은 일차원 배열로 구현 가능하다.

이진 탐색 트리 구현

좌/우측 자식으로 추가할 Node 클래스와 이진 탐색 트리인 BinarySearchTree 클래스를 선언한다.

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

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

const binaryTree = new BinarySearchTree();

삽입

다음은 이진 탐색 트리의 삽입, 삭제 부분을 구현한 것이다.

class BinarySearchTree {
  // ...code
  
  insert(value) {
    const node = new Node(value);
    if (this.root === null) {
      this.root = node;
      return;
    } 
    
    let currentNode = this.root;
    while (currentNode !== null) {
      if (currentNode.value < value) {
        if (currentNode.right === null) {
          currentNode.right = node;
          break;
        }
        currentNode = currentNode.right;
      } else {
        if (currentNode.left === null) {
          currentNode.left = node;
          break;
        }
        currentNode = currentNode.left;
      }
    }
  }
  
  // * * * recursion(재귀)로 구현 * * * //
  
  // insertNode(node, newNode) {
  //   if (newNode.value < node.value) {
  //     if (node.left === null) node.left = newNode;
  //     else this.insertNode(node.left, newNode);
  //   } else {
  //     if (node.right === null) node.right = newNode;
  //     else this.insertNode(node.right, newNode);
  //   }
  // }
  
  // insert(value) {
  //   const node = new Node(value);
  //   if (this.root === null) this.root = node;
  //   else this.insertNode(this.root, node);
  // }
}

const binaryTree = new BinarySearchTree();

binaryTree.insert(11);
binaryTree.insert(2);

루트 노드가 없다면 루트에 노드를 추가해주고 리턴하고, 루트 노드가 있다면 루트 노드부터 대소를 비교하면서 좌/우측 자식 노드로 계속 이동하여 맞는 자리에 위치하면 된다.

삭제

삭제는 조금 까다롭다. 고려해야하는 조건이 세 가지다.

삭제해야 하는 노드가

  1. 자식이 없는 노드(leaf node)인 경우
  2. 좌/우측 자식 중 하나의 자식만 있는 경우
  3. 좌/우측 자식이 다 있는 경우

이다.

삭제할 노드 탐색

class BinarySearchTree {
  // ...code
  
  removeNode(node, value) {
    if (node === null) return null;
    
    if (value < node.value) {
      node.left = this.removeNode(node.left, value);
      return node;
    } else if (value > node.value) {
      node.right = this.removeNode(node.right, value);
      return node;
    } else {
      // 삭제할 노드를 찾은 경우 code
    } 
    
  }
  
  remove(value) {
    this.root = this.removeNode(this.root, value);
  }
}

우선 재귀함수를 통해 루트 노드부터 출발하여 재귀함수가 실행되면서 삭제하려는 값을 찾고, 삭제까지 수행하도록 하였다. 삭제하려는 값을 입력 받아(value) 현재 노드의 값보다 작으면 좌측 노드로, 크면 우측 노드로 향하여 결국에는 값을 찾을 수 있도록 재귀를 실행한다.

그리고 삭제할 노드를 찾게 된다면 그 노드의 자식의 경우에 따라 나눈다.
트리 구조는 다음과 같다고 가정하고 설명한다.

                12
       5                  15
   3       7          13      17
1             9                   19
                              18

1. 자식이 없는 노드(leaf node)인 경우

removeNode(node, value) {
  // ... code
  // else 문 내부
  
  // 1. 자식이 없는 노드(leaf node)인 경우
  if (node.left === null && node.right === null) {
    node = null;
    return node;
  } 
}

1번 경우인 자식이 없는 노드인 경우에는 해당 노드를 null로 만들어주고 그 값을 리턴해주면 끝난다. 즉, 9번 노드를 삭제한다면 그냥 null로 만들어주고 재귀가 끝났을 때 5번 노드의 우측 노드가 9번 노드로 되도록 리턴해주면 된다.

2. 자식이 하나만 있는 경우

removeNode(node, value) {
  // ... code
  // else 문 내부
  
  // 2. 좌/우측 자식 중 하나의 자식만 있는 경우
  if (node.left === null) {
    node = node.right;
    return node;
  } else if (node.right === null) {
    node = node.left;
    return node;
  }
}

2번 경우인 자식이 하나만 있는 경우에는 해당 노드을 제거하고, 삭제된 노드의 부모와 자식을 연결해주면 된다. 

                12
       5                  15
   3       7          13      17
1             9                   19
                              18

예를 들어, 7번 노드를 삭제한다고 했을 때 부모 노드인 5번 노드와 삭제된 노드의 우측 자식인 9번 노드를 연결해주면 된다. 즉, 현재 노드를 우측 자식인 9번 노드로 재할당하고 그 노드 값을 리턴해주면 된다.

3. 자식이 둘 다 있는 경우

removeNode(node, value) {
  // ... code
  // else 문 내부
  
  // 3. 좌/우측 자식이 다 있는 경우
  let currentNode = node.right;
  let minValue = node.right.value;
  while (true) {
    if (currentNode.value < minValue) {
      minValue = currentNode.value;
    }
    if (currentNode.left !== null) {
      currentNode = currentNode.left;
    } else break;
  }

  const prevNode = node;
  node = currentNode;
  node.left = prevNode.left;
  return node;
}

3번 경우인 자식이 둘 다 있는 경우에는 두 가지 방법이 있다.

  1. 좌측 노드에서 가장 큰 값을 삭제될 노드에 갖다 놓는다.
  2. 우측 노드에서 가장 작은 값을 삭제될 노드에 갖다 놓는다.

여기서는 2번의 방법으로 구현해보았다. 위 트리로 예를 들면, 15번 노드를 삭제한다고 했을 때 15번 노드의 우측 자식 트리에서 가장 작은 17번 노드를 15번 노드에 갖다 놓으면 된다. 17번 노드를 15번 노드로 옮기면서 15번 노드의 왼쪽 자식인 13번 노드를 좌측 자식으로 연결해주면 된다.

코드에서는 현재 노드를 우측 자식으로 선언하고, 최소값을 담는 변수를 하나 더 선언하여 초기값은 우측 자식의 값으로 할당했다. 그리고 반복문을 돌려 현재 값이 최소값보다 작다면 최소값에 그 값을 재할당하고, 최소값이므로 좌측 자식만 확인하면 되기 때문에 현재 노드를 좌측 자식으로 재할당하며 좌측 자식이 null 값이 될 때가지 순회한다.

반복문이 끝나면 현재값에 우측 노드 트리 중에서 가장 작은 값을 가진 노드가 할당되어 있을 것이므로 노드를 최소값을 지닌 노드로 할당하고 좌측 노드를 삭제된 노드의 좌측 노드로 설정한다. 그리고 노드를 리턴해주면 끝이 난다.

코드 전체는 다음과 같다.

class BinarySearchTree {
  // ... code
  
  removeNode(node, value) {
    if (node === null) return null;
    
    if (value < node.value) {
      node.left = this.removeNode(node.left, value);
      return node;
    } else if (value > node.value) {
      node.right = this.removeNode(node.right, value);
      return node;
    } else {
      // 1. 자식이 없는 노드(leaf node)인 경우
      if (node.left === null && node.right === null) {
        node = null;
        return node;
      } 
      
      // 2. 좌/우측 자식 중 하나의 자식만 있는 경우
      if (node.left === null) {
        node = node.right;
        return node;
      } else if (node.right === null) {
        node = node.left;
        return node;
      }
      
      // 3. 좌/우측 자식이 다 있는 경우
      let currentNode = node.right;
      let minValue = node.right.value;
      while (true) {
        if (currentNode.value < minValue) {
          minValue = currentNode.value;
        }
        if (currentNode.left !== null) {
          currentNode = currentNode.left;
        } else break;
      }
      
      const prevNode = node;
      node = currentNode;
      node.left = prevNode.left;
      return node;
    }
  }
  
  remove(value) {
    this.root = this.removeNode(this.root, value);
  }
}

const binaryTree = new BinarySearchTree();

이진 트리 순회

트리의 모든 노드를 방문해서 각 노드마다 어떤 작업을 수행하는 것을 트리 순회라고 한다. 순회를 하는 방법에는 최상위에서 하위로 내려가는지, 최하위부터 상위로 올라가는지, 좌/우의 우선순위 등을 고려하여 중위, 전위, 후위순회 세 가지로 분류된다.

중위순회

중위순회는 왼쪽 하위트리를 방문 후 루트를 방문하여 오른쪽 하위트리까지 방문하는 것이다.

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

class BinaryTree {
  constructor(root) {
    this.root = root;
  }
  
  inOrderTraverseNode(node, arr) {
    if (node !== null) {
      this.inOrderTraverseNode(node.left, arr);
      arr.push(node.value);
      this.inOrderTraverseNode(node.right, arr);
    }
  }

  inOrderTraverse() {
    const arr = [];
    this.inOrderTraverseNode(this.root, arr);
    console.log(arr);
  }
}

const binaryTree = new BinaryTree(new Node(9));
binaryTree.root.left = new Node(3);
binaryTree.root.right = new Node(8);
binaryTree.root.left.left = new Node(2);
binaryTree.root.left.right = new Node(5);
binaryTree.root.right.right = new Node(7);
binaryTree.root.left.right.right = new Node(4);
binaryTree.inOrderTraverse();

현재 이진 트리는 다음과 같다.

      9
  3       8
2   5       7
      4

중위순회는 왼쪽 하위 트리부터 방문해야하므로 노드 2까지 내려가야 한다. 따라서 재귀함수를 이용해 왼쪽 노드의 최하위까지 내려가도록 한다. 따라서 루트 노드인 9부터 시작해서 3, 2를 방문 후 노드 2 이후에는 자식이 없기 때문에 재귀가 종료되어 배열에 노드 2가 담긴다. 노드 3의 좌측 노드 재귀가 끝났으니 노드 3도 배열에 담기고, 우측 노드을 마찬가지로 순회한다. 이렇게 순회하며 루드의 왼쪽 트리의 순회가 끝나면 오른쪽 트리를 마저 같은 방법으로 순회하고 종료된다.

따라서 결과는 [ 2, 3, 5, 4, 9, 8, 7 ]로 나온다.

전위순회

전위순회는 루트를 먼저 방문하고 좌측 노드부터 방문한 후에 우측 노드를 방문하는 것이다. 따라서 위의 중위순회 코드에서 우측/좌측 재귀의 위치만 바꿔주면 된다.

class BinaryTree {
  constructor(root) {
    this.root = root;
  }
  
  preOrderTraverseNode(node, arr) {
    if (node !== null) {
      arr.push(node.value);
      this.preOrderTraverseNode(node.left, arr);
      this.preOrderTraverseNode(node.right, arr);
    }
  }
  
  preOrderTraverse() {
    const arr = [];
    this.preOrderTraverseNode(this.root, arr);
    console.log(arr);
  }
}

트리의 구조가 중위순회의 예시와 같다고 할 때, 결과는 [ 9, 3, 2, 5, 4, 8, 7 ]로 나온다.

후위순회

후위순회는 하위 트리를 모두 방문 후 루트를 방문하는 것이다. 좌측 노드를 먼저 방문하고 그 다음 우측 노드, 마지막으로 노드 자신을 방문한다.

class BinaryTree {
  constructor(root) {
    this.root = root;
  }
  
 postOrderTraverseNode(node, arr) {
    if (node !== null) {
      this.postOrderTraverseNode(node.left, arr);
      this.postOrderTraverseNode(node.right, arr);
      arr.push(node.value);
    }
  }

  postOrderTraverse() {
    const arr = [];
    this.postOrderTraverseNode(this.root, arr);
    console.log(arr);
  }
}

결과는 [ 2, 4, 5, 3, 7, 8, 9 ]으로 출력된다.

만약 제가 고려하지 못한 부분이 있다면 알려주세요, 감사합니다 :)

profile
yoon
얼레벌레 개발자
이전 포스트

[Data Structure & Algorithm] 연결 리스트 개념과 구현

다음 포스트

[Data Structure & Algorithm] 힙(Heap)의 개념과 구현

0개의 댓글