Tree (Tree란? Binary Search Tree란? Balanced tree란? - Red-black tree)

Posted on Edited on In ,

Tree 소개

 

Terminology

  • Root node: 가장 상단의 node이며 parent node가 없음.
  • Leaf node: 가장 하단에 위치한 node들이며 child node가 없음.
  • Subtree: 중간 단계에서 특정 node 이하의 모든 node를 포함한 트리를 subtree라고 부름.
  • Parent node: Root node를 제외한 node 들 중 child node를 가지고 있는 node들.
  • Ancestor Node: Root node와 어떤 특정 node 사이에 끼어있는 node들.
  • Key: node가 가지고 있는 값.
  • Level: node의 층. Root node는 항상 level 1, 그 다음 층부터 ++.

트리 순회

  • Pre-order traversal
    • 현재 node를 먼저 방문. 그 다음 왼쪽 하위 node를, 그 후 오른쪽 하위 node를 재귀적으로 방문.
  • In-order traversal
    • 왼쪽 node를 먼저 방문, 그 다음 현재 node, 그 후 오른쪽 node 방문.
  • Post-order traversal
    • 두 자식 node를 먼저 방문, 그 후 현재 node 방문.
  • Level-order traversal
    • 트리의 맨 위 레벨부터 아래 레벨까지, 왼쪽에서 오른쪽 노드 순서로 방문.

 

BST (Binary Search Tree)

BST 특징

drawing

  • 부모 노드의 값 왼쪽 자식 노드의 값
    • 부모 노드보다 작거나 같은 모든 데이터 원소는 항상 왼쪽에 위치
  • 부모 노드의 값 오른쪽 자식 노드의 값
    • 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 위치
  • 원소 검색을 할 때, 각 level마다 검색 범위가 절반으로 줄어듬.
    • 즉, 트리의 모든 원소를 방문하지 않아도 됨.
  • 트리의 높이
  • 데이터 노드 검색 또는 삽입 동작

BST 원소 삽입

  • 그냥 downstream으로 추가하면 됨

BST 원소 삭제

  • node 삭제 후에도 BST 속성을 만족하도록 기존의 하위단 node를 끌어올려와야함.
  • 삭제할 node에게
    • child node가 없으면 그냥 지움
    • child node가 1개면 자리를 계승시킴.
    • child node가 2개면 현재 삭제하는 node보다 더 큰 숫자의 node가 자리를 계승함.

 

Balanced tree (AVL, red-black tree)

BST 의 단점

  • 데이터가 sort된 상태에서 가장 작은 숫자를 root node로 만들고, 그 후 작은 순서대로 insert를 하게 된다면, 한쪽으로 치우쳐진 tree가 생길 것이다.
    • 비슷한 예제로, 역방향 sort + 가장 큰 숫자를 root node로 만듬 + 큰 순서대로 insert를 하면 역시 또 한쪽으로 치우쳐진 tree가 생긴다.
  • find()함수의 시간 복잡도는 이다.
  • 그렇기에 tree의 높이는 최적화 되야한다.
    • 이 작업을 ‘balancing’이라고 한다.
    • 이 작업을 자동으로 하면 ‘self-balancing’이 된다.
  • self-balancing tree의 종류에는 AVL tree와 red-black tree가 있다.
    • std::map이 red-black tree 형태로 구현되어있다.
    • 왜 red-black tree로 되어있을까?
      • AVL tree의 rebalancing rotation은
      • Red-black tree의 rebalancing rotation은 이다.
      • “Why is std::map implemented as a red-black tree?”
Related Posts