트리

이진트리

function BinaryTree() {
    this._root = null;
}

선순위 순회 : 루트, 왼쪽, 오른쪽순

BinaryTree.prototype.traversePreOrder = function () {
  traverseInOrderHelper(this._root);

  function traverseInOrderHelper(node) {
    if (!node) return;
    console.log(node.value);
    traverseInOrderHelper(node.left);
    traverseInOrderHelper(node.right);
  }
};

중순위 순회 : 왼쪽, 루트, 오른쪽 순

BinaryTree.prototype.traverseInOrder = function() {
    traverseInOrderHelper(this._root);

    function traverseInOrderHelper(node) {
        if (!node)
            return;
        traverseInOrderHelper(node.left);
        console.log(node.value);
        traverseInOrderHelper(node.right);
    }
}

후순위 순회 : 왼쪽, 오른쪽, 루트 순

BinaryTree.prototype.traversePostOrder = function() {
    traversePostOrderHelper(this._root);

    function traversePostOrderHelper(node) {
        if (node.left)
            traversePostOrderHelper(node.left);
        if (node.right)
            traversePostOrderHelper(node.right);
        console.log(node.value);
    }
}

단계순위 순회(너비 우선 검색 BFS:breadth first search) : 각 노드 단계를 방문(깊게x 차례대로)

BinaryTree.prototype.traverseLevelOrder = function() {
    // Breath first search
    var root = this._root,
        queue = [];

    if (!root)
        return;
    queue.push(root);

    while (queue.length) {
        var temp = queue.shift();
        console.log(temp.value);
        if (temp.left)
            queue.push(temp.left);
        if (temp.right)
            queue.push(temp.right);
    }
}

 

요약

잎 노드(자식 노드가 없는 노드)를 방문하기 전에 루트를 조사할 필요가 있는 경우 선순위 순회를 선택

부모 노드를 방문하기 전에 잎 노드를 먼저 조사해야 하는 경우 후순위 순회를 선택

트리의 노드 자체에 순서가 있어서 트리를 원래 순서대로 방문하고 싶은 경우 중순위 순회를 선택

후순위 순회는 트리가 생성된 순서와 다른 순서로 트리를 방문

시간 복잡도 : O(n)

 

이진 검색 트리 BST, binary search tree

왼쪽 자식이 부모보다 작고 오른쪽 자식이 부모보다 크다.

검색과 삽입, 특정 값을 지닌 노드 제거의 시간 복잡도가 O(log2(n))

 

function BinarySearchTree() {
    this._root = null;
}

삽입

루트가 빈 경우 루트가 신규 노드가 된다. 루트가 비어 있지 않다면 while 루프를 사용해 조건이 만족될 때까지 이진 검색 트리를 순회한다. 각 루프 반복 시 신규 노드가 현재 루트보다 크거나 작은지 확인한다.

BinarySearchTree.prototype.insert = function(value) {
    var thisNode = {
        left: null,
        right: null,
        value: value
    };
    if (!this._root) {
        //if there is no root value yet
        this._root = thisNode;
    } else {
        //loop traverse until
        var currentRoot = this._root;
        while (true) {
            if (currentRoot.value > value) {
                //let's increment if it's not a null and insert if it is a null
                if (currentRoot.left != null) {
                    currentRoot = currentRoot.left;
                } else {
                    currentRoot.left = thisNode;
                    break;
                }
            } else if (currentRoot.value < value) {
                //if bigger than current, put it on the right
                //let's increment if it's not a null and insert if it is a null
                if (currentRoot.right != null) {
                    currentRoot = currentRoot.right;
                } else {
                    currentRoot.right = thisNode;
                    break;
                }
            } else {
                //case that both are the same
                break;
            }
        }
    }
}

시간 복잡도(균형 트리) : O(log2(n))

시간 복잡도(불균형 트리) : O(n)

 

삭제

삭제 알고리즘은 우선 삭제하고자 하는 값을 지닌 노드를 찾기 위해 트리를 순회한다. 해당 노드를 찾은 경우 다음 세 가지 경우가 있다.

1. 노드에 자식이 없다 - null을 반환

2. 노드에 자식이 하나 있다. - 현재 자식을 반환. 해당 자식이 위 단계로 올라가서 부모를 대체

3. 노드에 자식이 두 개 있다. 왼쪽 하위 트리의 최대치를 찾거나 오른쪽 하위 트리의 최소치를 찾아서 해당 노드를 대체

BinarySearchTree.prototype.remove = function(value) {

    return deleteRecursively(this._root, value);

    function deleteRecursively(root, value) {
        if (!root) {
            return null;
        } else if (value < root.value) {
            root.left = deleteRecursively(root.left, value);
        } else if (value > root.value) {
            root.right = deleteRecursively(root.right, value);
        } else {
            //no child
            if (!root.left && !root.right) {
                return null; // case 1
            } else if (!root.left) { // case 2
                root = root.right;
                return root;
            } else if (!root.right) { // case 2
                root = root.left;
                return root;
            } else {
                var temp = findMin(root.right); // case 3
                root.value = temp.value;
                root.right = deleteRecursively(root.right, temp.value);
                return root;
            }
        }
        return root;
    }

    function findMin(root) {
        while (root.left) {
            root = root.left;
        }
        return root;
    }
}

시간 복잡도(균형 트리): O(log2(n))

시간 복잡도(불균형 트리): O(n)

 

검색

BinarySearchTree.prototype.findNode = function(value) {
    var currentRoot = this._root,
        found = false;
    while (currentRoot) {
        if (currentRoot.value > value) {
            currentRoot = currentRoot.left;
        } else if (currentRoot.value < value) {
            currentRoot = currentRoot.right;
        } else {
            //we've found the node
            found = true;
            break;
        }
    }
}

var bst1 = new BinarySearchTree();
bst1.insert(1);
bst1.insert(3);
bst1.insert(2);
bst1.findNode(3); // true
bst1.findNode(5); // false
console.log(bst1);

AVL 트리

AVL은 스스로 균형을 잡는 이진 검색 트리다.

function AVLTree(value) {
  this.left = null;
  this.right = null;
  this.value = value;
  this.depth = 1;
}

AVL 트리의 높이

AVLTree.prototype.setDepthBasedOnChildren = function () {
  if (this.node == null) {
    this.depth = 1;
  }

  if (this.left != null) {
    this.depth = this.left.depth + 1;
  }
  if (this.right != null && this.depth <= this.right.depth) {
    this.depth = this.right.depth + 1;
  }
};

단일 회전 ㅆ바련ㄴ이 좇같이 해놧ㄴ[

왼쪽 회전

AVLTree.prototype.rotateLL = function () {
  var valueBefore = this.value;
  var rightBefore = this.right;
  this.value = this.left.value;

  this.right = this.left;
  this.left = this.left.left;
  this.right.left = this.right.right;
  this.right.right = rightBefore;
  this.right.value = valueBefore;

  this.right.setDepthBasedOnChildren();
  this.setDepthBasedOnChildren();
};

오른쪽 회전

AVLTree.prototype.rotateRR = function () {
  // the right side is too long => rotate from the right (_not_ rightwards)
  var valueBefore = this.value;
  var leftBefore = this.left;
  this.value = this.right.value;

  this.left = this.right;
  this.right = this.right.right;
  this.left.right = this.left.left;
  this.left.left = leftBefore;
  this.left.value = valueBefore;

  this.left.setDepthBasedOnChildren();
  this.setDepthBasedOnChildren();
};

이중 회전

한번의 회전을 한 이후에도 AVL 트리가 여전히 불균형이라면 완전한 균형을 위해 두번 회전해야 한다.

오른쪽 왼쪽 회전(오른쪽 이후에 왼쪽)

왼쪽 오른쪽 회전(왼쪽 이후에 오른쪽)

 

트리 균형 잡기

AVLTree.prototype.balance = function () {
  var ldepth = this.left == null ? 0 : this.left.depth;
  var rdepth = this.right == null ? 0 : this.right.depth;

  if (ldepth > rdepth + 1) {
    // LR or LL rotation
    var lldepth = this.left.left == null ? 0 : this.left.left.depth;
    var lrdepth = this.left.right == null ? 0 : this.left.right.depth;

    if (lldepth < lrdepth) {
      // LR rotation consists of a RR rotation of the left child
      this.left.rotateRR();
      // plus a LL rotation of this node, which happens anyway
    }
    this.rotateLL();
  } else if (ldepth + 1 < rdepth) {
    // RR or RL rorarion
    var rrdepth = this.right.right == null ? 0 : this.right.right.depth;
    var rldepth = this.right.left == null ? 0 : this.right.left.depth;

    if (rldepth > rrdepth) {
      // RR rotation consists of a LL rotation of the right child
      this.right.rotateLL();
      // plus a RR rotation of this node, which happens anyway
    }
    this.rotateRR();
  }
};

삽입

AVLTree.prototype.insert = function (value) {
  var childInserted = false;
  if (value == this.value) {
    return false; // should be all unique
  } else if (value < this.value) {
    if (this.left == null) {
      this.left = new AVLTree(value);
      childInserted = true;
    } else {
      childInserted = this.left.insert(value);
      if (childInserted == true) this.balance();
    }
  } else if (value > this.value) {
    if (this.right == null) {
      this.right = new AVLTree(value);
      childInserted = true;
    } else {
      childInserted = this.right.insert(value);

      if (childInserted == true) this.balance();
    }
  }
  if (childInserted == true) this.setDepthBasedOnChildren();
  return childInserted;
};

시간 복잡도:O(nlog2(n))

공간 복잡도:O(nlog2(n))

 

삭제

AVLTree.prototype.remove = function (value) {
  return deleteRecursively(this, value);

  function deleteRecursively(root, value) {
    if (!root) {
      return null;
    } else if (value < root.value) {
      root.left = deleteRecursively(root.left, value);
    } else if (value > root.value) {
      root.right = deleteRecursively(root.right, value);
    } else {
      //no child
      if (!root.left && !root.right) {
        return null; // case 1
      } else if (!root.left) {
        root = root.right;
        return root;
      } else if (!root.right) {
        root = root.left;
        return root;
      } else {
        var temp = findMin(root.right);
        root.value = temp.value;
        root.right = deleteRecursively(root.right, temp.value);
        return root;
      }
    }
    root.setDepthBasedOnChildren(); // ONLY DIFFERENCE from the BST one
    return root;
  }

  function findMin(root) {
    while (root.left) root = root.left;
    return root;
  }
};

dd

var avlTest = new AVLTree(1, "");
avlTest.insert(2);
avlTest.insert(3);
avlTest.insert(4);
avlTest.insert(5);
avlTest.insert(123);
avlTest.insert(203);
avlTest.insert(2222);
console.log(avlTest);