[TIL][DataStructure] Tree & BST

Tree는...

노드들로 이루어진 계층적 자료구조이다. 자료구조 보다 DOM에 관하여 먼저 알게된 나는
DOM Tree과 비슷한 구조로 생각되어 가장 친숙한 자료구조 였다.

가장 위의 노드를 Root 라 칭하며 Root를 필두로 그 아래로 자손들이 줄줄이 이어지는 형태로
기본적으로 Child(자식) 노드의 갯수 및 정렬 형태에는 제한이 없다.
또한 반드시 자식을 가져야 하는 강제성도 없다.
그러나 Root를 제외한 각각의 노드는 무조건 Parent(부모) 노드가 존재하며, 경우에 따라 같은 부모에게서 갈라져 나온 Sibling(형제) 이 존재할 수 있다.
더이상 자식이 없는 노드는 나무(Tree)의 끝, 잎사귀(Leaf) 라 한다.
부모와 자식을 이어주는 선은 Edge라 칭한다!

또한 트리에는 Depth와 Height의 속성이 존재하는데, 루트를 기준으로 다른 노드에 접근하기 위한 거리를 Depth라 정의하며, 이때 Root는 Depth가 0이 된다.
Height의 경우 말 그대로 가장 높은 Depth의 Leaf 부터 시작하여 위로 한단계씩 올라가게 되며, 가장 최하의 Leaf가 Height 0 이 되며, Root는 가장 높은 Height를 가지게 된다.

Tree의 종류는...

각 부모의 자식이 최대 2개인 트리구조를 Binary Tree(이진 트리) 라 하며, 각 구조에 따라 한번 더 종류를 나눌 수 있는데

1. Complete Binary Tree 완전 이진 트리
각 노드는 왼쪽 우선으로 채워져 있으며, 마지막 노드를 제외하고 전부 자식을 갖고있다.
2. Perfect Binary Tree 포화 이진 트리
마지막 leaf를 제외한 모든 노드가 자식을 2개씩 갖고있으며, leaf들의 depth가 동일하다.
3. Skewed Binary Tree 편향 이진 트리

모든 노드들이 한 방향으로 연결된 트리이다. 사실상 Linked List와 비슷하다.

또한

BST - Binary Search Tree 라는 구조가 존재하는데

각 부모 노드는 binary tree 와 마찬가지로 최대 2개의 노드를 자식으로 가질 수 있으나, 자신보다 값이 작은 노드는 왼쪽, 값이 크거나 같은 노드는 오른쪽 으로 들어가게 된다.

이를 통해 규칙성을 갖게되어 특정 값을 찾게 될 때 O(n)의 시간복잡도를 갖는 Tree, Binary Tree에 비해 빠른 O(log n)의 시간복잡도를 갖게 된다!

해당 BST를 순회하기 위한 방법은 세가지가 있는데,

1. Preorder Traversal 전위순회
부모를 처음으로, 적은 값을 가진 왼쪽 자식, 크거나 같은 값을 가진 오른쪽 자식 순으로 순회한다.
2. Inorder Traversal 중위순회
적은 값을 가진 왼쪽 자식을 먼저, 그후 부모, 크거나 같은 값을 가진 오른쪽 자식 순으로 순회한다.
3. Postorder Traversal 후위순회
왼쪽과, 오른쪽 자식을 먼저 순회 후 부모를 가장 늦게 탐색한다.

가장 중요하다 생각되는 BST 를 JS로 구현하였다!

class BinarySearchTreeNode {		// BST 노드 생성자
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  insert(value) {			// 트리에 Node를 추가하는 method
    let node = new BinarySearchTreeNode(value);
    function recursion(el) {
      if(value >= el.value) {
        if(el.right === null) {
          el.right = node;
        }
        else {
          recursion(el.right);
        }
      }
      else if(value < el.value) {
        if(el.left === null) {
          el.left = node;
        }
        else {
          recursion(el.left);
        }
      }
    }
    recursion(this);
  }
  contains(value) { 			//  해당 값을 가진 Node가 존재하는지 반환하는 method
    let result = false;
    function recursion(el) {
      let root = el;
      if(el.value === value) {
        result = true;
        return;
      }
      else {
        if(el.value > value) {
          if(el.left) {
            root = el.left;
            recursion(root);
          }
        }
        else if(el.value <= value) {
          if(el.right) {
            root = el.right;
            recursion(root);
          }
        }
      }
    }
    recursion(this);
    return result;
  }
  inorder(callback) {			// 트리를 순회하여 콜백 함수를 통해 특정 행동을 하는 method
    let rootNode = this;
    function recursion(node){
      let leftNode=node.left;
      let rightNode=node.right;
      if(leftNode){
        recursion(leftNode);
      } 
      callback(node.value);
      if(rightNode){ 
        recursion(rightNode);
      }
    }
    recursion(rootNode);
  }
}

BST 및 Tree를 구현 해보고 느낀점은 재귀의 중요성이다... Dom tree 를 순회할 때도 힘었지만 이번 BST를 구현해보며 아직 재귀를 100% 정복하지 못했다는 것을 느꼈다...
특히 마지막 중위순회 같은경우 아직도 정확히 이해하지 못했으니 공부가 더 필요할것 같다.
Tree 자료구조는 웹,앱 개발자 입장에서 취업에 있어서 중요도가 높다고 하니 좀 더 파볼 필요가 있을것 같다!!!