이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

게시글

강좌13 - Algorithm - 2년 전 등록 / 25일 전 수정

자료구조(트리, tree)

조회수:
0
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

안녕하세요! 이번 시간에는 트리에 대해 알아보겠습니다!

이름이 트리인 이유는 나무처럼 생겼기 때문입니다. (정확히는 나무를 거꾸로 뒤집어놓았습니다.) 간단한 예로 HTML 구조가 있습니다. root(뿌리)부터 시작해서 아래로 가지치기를 합니다. 그래서 제일 마지막 노드는 뭐라고 부를까요? 바로 leaf(잎)입니다. 제일 위는 root고 제일 아래는 leaf니까 완전 나무를 거꾸로 뒤집어 놓은 거죠? root도 leaf도 아닌 노드들은 내부 노드라고 부릅니다.

undefined

노드와 노드 사이를 이어주는 것은 branchedge라고 부릅니다. 시작점은 반드시 root 하나여야 합니다. HTML을 배웠으면 아시겠지만, 부모자식 관계, 형제자매 관계, 조상, 후손 등이 그대로 적용됩니다. 사실 HTML이 트리를 본딴 구조라서 그렇습니다.

그리고 위의 그림에서 document부터 마지막 Text까지 가는 길을 경로(path)라고 부릅니다. 그리고 부모노드에서 자식노드 사이의 edge 개수를 높이(height)라고 부릅니다. 예를 들면, 위의 경우에서 document root에서 Text "DOM Tree"까지의 높이는 4입니다. (화살표 4개를 거쳐왔기 때문)

트리에서 유의해야할 점은 트리의 아랫 부분도 모두 트리라는 겁니다. root가 없다고 생각해보세요. 그래도 트리죠? 또 Element<body>가 root라고 생각해보세요. 그것도 트리죠. 이렇게 트리 아래에 계속 트리가 나오기 때문에 재귀 함수가 사용됩니다.

실생활에도 트리는 엄청 많이 사용되는데요. 대진표, 지휘계통 등 단계나 계층이 있는 곳에서는 어김없이 사용됩니다. 그러니 트리에 대해 꼭 알아야겠죠? 그 중에서 우리는 자식을 최대 2개까지만 가질 수 있는 이진 트리에 대해 알아볼 겁니다. 또 우리는 이 시간에 이진 트리 중에서 이진 검색 트리에 대해 다룹니다. 왜 굳이 이진 검색 트리냐면, 중복 데이터가 없다는 가정 하에 크다와 작다를 쉽게 구분할 수 있기 때문입니다. 따라서 한 번 정렬하면 빠르게 찾을 수 있습니다. (O(lgn)) 사실 일반 트리도 모두 이진 트리로 변형할 수 있지만 그 방법은 여기서 다루지 않겠습니다. 궁금하시면 개인적으로 메일 주세요.

undefined

이진 검색 트리는 위와 같이 생겼습니다. 잘 보시면 숫자가 정렬된 것을 알 수 있습니다. 가장 작은 숫자는 가장 왼쪽에, 가장 큰 숫자는 가장 오른쪽에 있습니다. 코드로 만들어볼까요? 트리는 지금까지의 자료구조와 코드의 복잡성이 차원이 완전 다릅니다. 또한 트리를 만드는 방법에 주의하셔야합니다. 트리에 데이터를 넣을 때나 찾을 때, 제거할 때 대부분 재귀를 사용합니다. 그리고 자료구조에서 처음으로 비공개함수(private)가 사용되었습니다. 재귀 함수를 비공개함수 처리하여 재사용성을 높였습니다.

var Tree = (function() {
  function Tree() {
    this.count = 0;
    this.root;
  }
  function Node(data) {
    this.data = data;
    this.left;
    this.right;
  }
  function _insert(root, node) {
    if (!root) return node;
    if (node.data < root.data) {
      root.left = _insert(root.left, node);
      return root;
    } else {
      root.right = _insert(root.right, node);
      return root;
    }
    return root;
  }
  Tree.prototype.add = function(data) {
    var node = new Node(data);
    if (this.count == 0) {
      this.root = node;
    } else {
      _insert(this.root, node);
    }
    return ++this.count;
  };
  function _get(data, node) {
    if (node) {
      if (data < node.data) {
        return _get(data, node.left);
      } else if (data > node.data) {
        return _get(data, node.right);
      } else {
        return node;
      }
    } else {
      return null;
    }
  }
  Tree.prototype.get = function(data) {
    if (this.root) {
      return _get(data, this.root);
    } else {
      return null;
    }
  };
  function _remove(root, data) {
    var newRoot, exchange, temp;
    if (!root) return false;
    if (data < root.data) {
      root.left = _remove(root.left, data);
    } else if (data > root.data) {
      root.right = _remove(root.right, data);
    } else {
      if (!root.left) {
        newRoot = root.right;
        // root 메모리 정리
        return newRoot;
      } else if (!root.right) {
        newRoot = root.left;
        // root 메모리 정리
        return newRoot;
      } else {
        exchange = root.left;
        while (exchange.right) exchange = exchange.right;
        temp = root.data;
        root.data = exchange.data;
        exchange.data = temp;
        root.left = _remove(root.left, exchange.data);
      }
    }
    return root;
  }
  Tree.prototype.remove = function(key) {
    var node = _remove(this.root, key);
    if (node) {
      this.root = node;
      this.count--;
      if (this.count == 0) this.root = null;
    }
    return true;
  };
  return Tree;
})();
var tree = new Tree();
tree.add(5); // 1
tree.add(3); // 2
tree.add(4); // 3
tree.add(2); // 4
tree.add(7); // 5
tree.add(6); // 6
tree.root.left.data; // 3
tree.root.left.left.data; // 2;
tree.root.left.right.data; // 4
tree;
tree.remove(3);
tree.root.left.data;

추가하는 것은 원하는 위치를 찾을 때까지 오른쪽 왼쪽 찾아가며 재귀를 통해 도달합니다. 찾는 것도 마찬가지죠. 지우는 게 문제입니다. 지우고자 하는 데이터를 재귀를 통해 찾아 지우면 되겠지만, 지운 후 트리가 이진 검색 트리 조건을 만족하는 지 확인해야 합니다.

따라서 지울 때 크게 세 가지 경우를 고려하게 됩니다. 

  1. 왼쪽 자식 노드가 없을 때(숫자 10 노드처럼)
  2. 오른쪽 자식 노드만 없을 때(숫자 14 노드처럼)
  3. 그리고 왼쪽, 오른쪽 자식 노드 둘 다 있을 때(숫자 8)입니다.

양쪽 자식 노드가 모두 없을 때는 1. 왼쪽 노드가 없을 때와 같이 처리합니다(사실 그냥 노드를 뺀 것과 동일합니다).

undefined

왼쪽 자식 노드가 없다면(숫자 10의 경우) 오른쪽 노드를 끌어올려 지워진 공간을 채우면 되고, 오른쪽 자식 노드가 없다면(숫자 14의 경우) 왼쪽 노드를 끌어올리면 되는데요. 

자식이 양쪽 다 있을 때(숫자 8의 경우)는 조금 다른 전략이 필요합니다. 일단 지우고자 하는 8 노드와 8의 왼쪽 자식 노드 중 가장 큰 노드(7)를 교환합니다. 그래야 이진 검색 트리 조건이 유지됩니다.

undefined

이제 7이 루트가 되고, 8은 7 자리로 교환되었습니다. 이후 3을 루트로 하는 트리에서 8을 지우면 됩니다. 현재 노드 8은 양쪽 자식이 모두 없으므로 1. 왼쪽 자식 노드가 없을 때의 조건에 해당합니다.

undefined

8을 지워버리면 새로운 이진 검색 트리가 완성됩니다. 이진 검색 트리의 삭제 기능은 노드의 자식 위치와 개수에 따라 분기 처리를 해주어야 해서 조금 더 복잡한 감이 있습니다.

다음 시간에는 에 대해 알아보겠습니다!

목록
투표로 게시글에 관해 피드백을 해주시면 많은 도움이 됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright © 2016- 무단 전재 및 재배포 금지

댓글

4개의 댓글이 있습니다.
2달 전
BST는 왼쪽 서브트리의 값은 ROOT보다 작고 오른쪽 서브트리는 ROOT보다 커야합니다.
그렇기때문에 삽입할때도 본인 값과 비교해서 오른쪽 혹은 왼쪽으로 이동합니다.
맨 아래그림을 보면 ROOT가 3임에도 불구하고 왼쪽 서브트리에 6 4 7 이 존재합니다.
BST에 어긋나죠
function _get(data, node) {
if (node) {
if (data < node.data) {
return _get(data, node.left);
} else if (data > node.data) {
return _get(data, node.right);
} else {
return node;
}
} else {
return null;
}
}
7을 찾기위해서 오른쪽으로 이동할텐데 그림에서는 왼쪽에 존재하죠

분명히 구현에서는
exchange = root.left;
while (exchange.right) exchange = exchange.right;
왼쪽서브트리로 이동하고 왼쪽서브트리에서 가장큰 값과 교환하여 삭제를 진행하고있습니다.
즉 8보다 작으면서 가장큰값은 7이며 8과 7과의 교환이 일어나야 BST를 유지합니다.
2달 전
아 제가 기초적인 실수를 했네요. 그림 수정하겠습니다. 감사합니다!
2달 전
문장들이 굉장히 햇갈립니다.
왼쪽 노드가 없을 때(숫자 10), 오른쪽 노드만 없을 때(숫자 14), 그리고 왼쪽, 오른쪽 둘 다 있을 때(숫자 8)입니다. 둘 다 없을 때는 왼쪽 노드가 없을 때로 칩니다. 잘못 이해하면 4가지같이 보이기때문에

1. 삭제할 노드가 단말노드인 경우 (리프 노드)
2. 삭제할 노드가 하나의 자식 노드를 갖는 경우 (왼쪽 혹은 오른쪽)
3. 삭제할 노드가 두개의 자식노드를 갖는 경우
가 좀 더 명확해보입니다.

문제는 둘 다 있을 때(숫자 8의 경우)는 어느 쪽 노드를 끌어올려 지워진 빈 공간을 채워야하는지 의문입니다. 저는 왼쪽(숫자 3)을 지워야할 것(숫자 8)과 교환한 후 삭제 메소드의 재귀를 통해 없애버렸습니다.
-> 자식노드가 두개있는경우 왼쪽자식으로 대체할 것인지 오른쪽 자식노드로 대체할 것인지 결정해야 합니다. 왼쪽자식 으로 채울경우 왼쪽 서브트리중 가장큰 값으로 대체해야하며, 오른자식노드로 채울경우 오른쪽 서브트리중 가장 작은 값으로 대체해야합니다.

코드 구현은 맞으나 예제가 틀렸습니다. 숫자 8를 삭제하기위해서는 7이 root와 교환되어야 합니다. 현재 마지막 그림을 보면 BST조건에 어긋납니다.
2달 전
설명은 수정해보겠습니다~ 그런데 마지막 그림은 왜 BST 조건에 어긋나죠? 왼쪽이 작고, 오른쪽이 크고, 자식은 최대 2개까지, 모든 조건을 만족합니다.
일 년 전
삭제는 상당히 아리까리 하네요 그림 말고 예시로 add들을 한 상태에서 루트 5를 지웠더니 3은 없어졌습니다.
일 년 전
저는 정상적으로 루트5가 지워지네요. 다시 한 번 해보시겠어요?
2년 전
8번은 처음부터 노드가 2개가 있는데 왜 굳이끌어 자식 노드를 끌어올려서 삭제를 해야하는건가요?
2년 전
처음부터 노드가 2개 있다는 게 무슨 말씀이시죠? 삭제는 자식 노드가 없을 때만 가능합니다. 그래서 자식 노드와 먼저 바꿔준 후 가장 아래로 보내서 제거하는 겁니다.