자료구조

[자료구조] 트리, 이진트리, 이진탐색트리, 완전이진트리

그레고리력 2021. 3. 19. 11:00

트리와 그래프

  • 그래프 : 노드와 간선으로 표현, 사이클 가능, 루트노드 개념 없음, 부모-자식 개념 없음, 네트워크 모델
  • 트리 : 노드로 이루어진 자료구조, 사이클 불가능 루트노드 반드시 한 개, 모든 자식노드는 한 개의 부모노드를 가짐, 계층 모델

트리

  • 비선형 자료구조, 트리는 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조
  • 노드로 이루어진 자료구조(노드는 어떤 자료형으로도 표현 가능)
  • Terminal Node ( = leaf Node, 말단 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다.
  • Node (노드) : 트리를 구성하고 있는 각각의 요소를 의미한다.
  • Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다.
  • 하나의 루트노드, 루트노드는 0개 이상의 자식노드를 가짐, 자식노드는 0개 이상의 자식노드를 가짐
  • 사이클이 존재할 수 없음

이진트리(binary tree)

  • 이진트리는 각 노드가 최대 두 개의 자식을 갖는 투리

이진탐색트리(Binary Search Tree, BST)

  • 모든 왼쪽 자식들 <= n < 모든 오른쪽 자식들 속성이 모든 노드 n에 대해서 참이어야 함속성이 모든 노드 n에 대해서 참이어야 함
  • 즉 모든 노드에 대하여 아래 명제는 참이다.
  • 각 노드의 왼쪽 서브트리의 노드들은 해당 노드의 값보다 작은 값을 지닌다.
  • 각 노드의 오른쪽 서브트리의 노드들은 해당 노드의 값보다 큰 값을 지닌다.
  • 중복된 노드가 없어야 한다.(중복 가능한 경우로 정의하기도 함)

BST에서의 추가와 삭제

  • 노드 추가 위치를 최상단 노드부터 탐색
  • 적절한 자리에 새로운 노드를 추가하여 자리를 찾음
  • 자식노드가 없는 노드는 대상 노드만 삭제하면 삭제가 끝남
  • 자식노드가 하나인 경우 삭제하고 자식노드를 삭제 노드 자리로 이동하면 끝
  • 자식노드가 두개인 경우 대상 노드를 삭제하고 삭제한 노드 왼쪽 가지에서 최대 노드를 찾아 삭제한 노드의 위치로 이동시키면 끝

완전이진트리(Complete binary tree)

  • 트리의 모든 높이에서 노드가 다 차있음
  • 마지막 레벨은 꽉 차있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 함

전 이진 트리(full binary tree)

  • 모든 노드의 자식이 없거나 정확히 두개 있는 경우

포화 이진 트리(perfect binary tree)

  • 전 이진 트리이자 완전 이진 트리리이자 완전 이진 트리

이진트리 순회(Traversal)

  1. 중위 순회(post-order) :왼쪽가지, 현재노드, 오른쪽 가지 순서(left-node-right)
  2. 전위 순회(pre-order): 자식노드보다 현재 노드를 먼저 방문(node-left-right)
  3. 후위 순회(post-order): 모든 자식노드들을 방문하고 현재 노드를 방문(left-right-node)

이진힙(최소힙과 최대힙)

  • 최소힙은 완전이진트리 구조
  • 루트는 트리 전체에서 가장 작은 원소
  • 삽입의 경우 트리 가장 아래 레벨에서 시작한다.
  • 그 다음 완전이진트리에 위배되지 않도록 부모 노드와 교환해나간다.
  • 삭제의 경우 루트노드를 제거한 후 힙의 가장 마지막 원소와 교환한다.
  • 그 다음 완전이진트리에 위배되지 않도록 자식 노드와 교환해나간다.
  • 삽입과 삭제 연산의 시간복잡도는 O(logn)

그래프

그래프 탐색

깊이 우선 탐색 (Depth First Search: DFS)

  • 그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아간다라는 방법을 우선으로 탐색한다.
  • 일단 연결된 정점으로 탐색
  • Stack 사용

너비 우선 탐색 (Breadth First Search: BFS)

  • 그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다.
  • Tree 에서의 Level Order Traversal 형식으로 진행
  • Queue 사용

기타

  • 트라이 자료구조(내용 추가 예정)
  • Red Black Tree(내용 추가 예정)
  • Minimum Spanning Tree(최소신장트리) ,Kruskal Algorithm, Prim 알고리즘