tree

트리

리스트

  • 데이터에 순서를 매겨 늘어놓은 자료구조

## 트리

  • 데이터 사이의 계층 관계를 표현하는 자료구조
  • 노드와 가지
    • 트리의 각 노드는 가지를 통해 다른 노드와 연결됨
  • 루트
    • 트리의 가장 위쪽에 있는 노드
    • 트리마다 한 개만 존재
  • 비단말 노드
    • 리프를 제외한 모든 노드(루트도 포함)
    • 내부 노드
  • 부모
    • 어떤 노드와 가지가 연결되었을때 위쪽에 있는 노드
    • 노드의 부모는 하나
  • 자식
    • 어떤 노드와 가지가 연결되었을때 아래쪽에 있는 노드
    • 노드는 자식을 여러 개 가질 수 있음
  • 차수
    • 각 노드가 갖는 자식의 수
  • n진 트리
    • 모든 노드의 차수가 n이하인 트리
  • 형제
    • 부모가 같은 노드
  • 조상
    • 어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드
  • 자손
    • 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드
  • 레벨
    • 루트에서 얼마나 멀리 떨어져 있는가를 의미
    • 루트의 레벨은 0, 가지가 하나씩 아래로 내려갈 때 마다 레벨이 1 증가
  • 높이
    • 루트에서 가장 멀리 있는 리프까지의 거리
    • 레벨의 최댓값
  • 서브트리
    • 어떤 노드를 루트로 하고 그 자손으로 구성된 트리
  • 널 트리
    • 노드와 가지가 전혀 없는 트리

    • 빈 트리

      순서트리와 무순서트리

  • 순서트리
    • 형제 노드의 순서 관계가 있는 트리
  • 무순서트리

    • 형제 노드의 순서 관계를 구별하지 않는 트리

      순서트리의 검색

  • 순서트리의 노드를 스캔하는 방법
    • 너비 우선 검색(BFS)
    • 깊이 우선 검색(DFS)

너비 우선 검색

  • 폭 우선 검색, 가로검색, 수평검색
  • 낮은 레벨부터 왼쪽에서 오른쪽으로 검색
  • 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법

깊이 우선 검색

  • 세로검색, 수직검색
  • 리프에 도달해서 더 이상 검색할 곳이 없으면 부모 노드로 돌아가고 그 다음 자식 노드로 내려가서 검색하는 방법
  • 이진 트리에서 각 노드는 깊이 우선 검색에서 최대 3번 지나감
  • 어느 시점에서 실제로 노드를 방문하는지에 따라 세 종류의 스캔 방법이 있음
    • 전위 순회
      • 노드방문 -> 왼쪽 자식 -> 오른쪽 자식
    • 중앙 순회
      • 왼쪽 자식 -> 노드 방문 -> 오른쪽 자식
    • 후위 순회

      • 왼쪽 자식 -> 오른쪽 자식 -> 노드 방문

이진트리

  • 노드로 왼쪽 자식과 오른쪽 자식만 갖는 트리(순서 구분 있음)
    • 두 자식 가운데 하나 또는 둘 다 존재하지 않아도 무관
  • 왼쪽 자식과 오른쪽 자식을 구분하는 특징
  • 왼쪽 서브트리
    • 왼쪽 자식을 루트로 하는 서브트리
  • 오른쪽 서브트리
    • 오른쪽 자식을 루트로 하는 서브트리

완전 이진 트리

  • 루트부터 아래쪽 레벨로 노드가 가득 차 있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워진 이진 트리
  • 높이가 k인 완전 이진 트리가 가질 수 있는 최대 노드의 수는 2`k+1 - 1
  • n개의 노드를 저장할 수 있는 완전 이진 트리의 높이는 log2N
  • 너비 우선 검색에서 스캔하는 순서대로 각 노드에 0, 1, 2, …의 값을 부여하면 배열에 저장하는 인덱스와 일대일 대응 가능

균형 검색 트리

  • 이진 검색 트리의 경우 키의 오름차순으로 노드가 삽입되면 트리의 높이가 깊어지는 단점이 있음
  • 비어 있는 이진 검색 트리에 1, 2, 3, 4, 5 순으로 노드를 삽입하는 경우 직선 모양의 트리가 되며, 선형 리스트처럼 되어 빠른 검색을 할 수 없게 됨
  • 균형 검색 트리
    • 높이를 O(log N)으로 제한하여 고안된 검색 트리
  • 이진 균형 검색 트리
    • AVL 트리
    • 레드-블랙 트리
  • 다진 균형 검색 트리
    • B 트리

이진 검색 트리

  • 모든 노드가 아래 조건을 만족하는 이진 트리
    • 왼쪽 서브트리 노드의 키값은 자신의 노드 키값보다 작아야 한다
    • 오른쪽 서브트리 노드의 키값은 자신의 노드 키값보다 커야 한다(단, 키값이 같은 노드는 복수로 존재하지 않음)
  • 중위 순회에 따른 깊이 우선 검색 시 키값이 오름차순으로 나열

이진 검색 트리의 특성

  • 구조가 단순함
  • 중위 순회의 깊이 우선 검색을 하면 검색 속도가 빠름

이진 검색 트리의 검색 알고리즘

  1. 루트에 주목. 주목 노드를 p라고 설정
  2. p가 None이면 검색을 실패하고 종료
  3. 검색하는 키와 주목노드의 키를 비교

이진 검색 트리의 삽입 알고리즘

  1. 루트에 주목. 주목 노드를 node라고 설정
  2. 삽입하려는 키와 주목 노드의 키를 비교
  3. 2번 과정으로 돌아가서 반복

이진 검색 트리의 삭제

  • 자식 노드가 없는 노드를 삭제하는 경우
    • 삭제할 노드가 부모 노드의 왼쪽 자식이면 부모의 왼쪽 포인터를 None으로 업데이트
    • 삭제할 노드가 부모 노드의 오른쪽 자식이면 부모의 오른쪽 포인터를 None으로 업데이트
  • 자식 노드가 1개인 노드를 삭제하는 경우
    • 삭제할 노드가 부모 노드의 오른쪽 자식인 경우, 부모의 오른쪽 포인터가 삭제할 노드의 자식을 가리키도록 업데이트
    • 삭제할 노드가 부모 노드의 왼쪽 자식인 경우, 부모의 왼쪽 포인터가 삭제할 노드의 자식을 가리키도록 업데이트
  • 자식 노드가 2개인 노드를 삭제하는 경우
    • 삭제할 노드의 왼쪽 서브트리에서 키값이 가장 큰 노드를 검색
    • 검색한 노드를 삭제할 위치로 옮김
      • 검색한 노드의 데이터를 삭제할 노드 위치에 복사
    • 옮긴 노드를 삭제한 후
      • 옮긴 노드에서 자식이 없는 경우와 한개 있는 경우(왼쪽 자식)를 나눠서 처리
#data structure    #python   

December 05, 2023