이진트리(Binary Tree) 와 linked Structure

msung99·2022년 4월 7일
0
post-thumbnail

linked structure 로 트리 구현

트리 class를 구현시 노드 구조체가 어떻게 생겼는가?

Node 구조체 구성

  • 데이터 필드

  • parent필드 : parent 노드형 포인터 (부모의 position을 담을 멤버)

  • childern 시퀀스 필드 : childern노드형 포인터(position)들을 저장하는 시퀀스에 대한 포인터

    • 시퀀스는 보통 링크드리스트로 구현됨
    • 자식들의 position(노드형 포인터)들을 저장하고 있는 시퀀스의 주소값을 저장
    • 해당 시퀀스에서 첫번째 노드형 포인터에 대한 시작주소를 저장
    • 시퀀스의 각각의 position(노드형 포인터)들은 해당 자식 노드를 가리킴(해당 자식 노드의 주소값을 저장)

시퀀스의 형태

  • 자식들에 대한 position들을 저장하고 있는 시퀀스를 어떤 자료구조로 구현해야 효율적일까?
  1. 배열
  • 미리 사이즈를 지정해야함
  1. 벡터
  • 사이즈가 알아서 커짐. 공간 낭비x
  1. 링크드리스트

상세 분석

그림 예시)
1. root노드 구성요소

  • 데이터 필드에 B를 저장
  • parent 노드는 NULL 저장
  • childern 노드의 position(노드형 포인터) 3개를 저장한 시퀀스의 주소를 저장(시퀀스를 가리킴)
  1. 링크드리스트 형태로 구현된 시퀀스에 저장된 각각의 childern position들은 각각의 childern 시퀀스 노드 객체를 가리킴
    • 내 자식들의 position(주소값) 들을 링크드리스트 형태로 저장
  1. 노드 A (데이터 A를 저장하는 노드)
  • 데이터 A를 저장
  • parent 노드형 포인터(parent position)는 노드 B의 주소를 저장(노드 B를 가리킴)
  • childern이 없으므로 childern 시퀀스는 NULL이 된다
  1. 노드 D
  • 데이터 D를 저장
  • parent가 B이므로 parent position은 B를 가리킴(B의 주소를 저장)
  • childern들의 position에 대한 시퀀스의 포인터 : 크기가 2인 시퀀스의 시작 노드의 주소값을 저장
    • 시퀀스에서 2번째 노드형 포인터(position)은 노드 E에 대한 주소값을 저장(노드 E를 가리킴)
  1. 노드 E
  • 데이터 E를 저장
  • parent 필드 : D의 주소값 저장
  • 시퀀스 포인터 : 자식이 없으므로 NULL 저장

이진트리 복습

이진트리

  • 모든 internal 노드의 자식의 개수가 0또는 1또는 2
  • child이 ordered pair. left child와 right child 의 순서가 구분된다

proper binary tree : 자식의 개수가 0또는 2인 트리

활용분야 : 수식표현

  • internal 노드 : 연산자 저장
  • external 노드 : 피연산자 저장

Decision Tree (결정 트리)

  • internal 노드는 질문사항(yes/no 포함)
  • external 노드가 결정사항
    ex) 식사매뉴결정 - internal노드는 패스트푸트 먹을래?, 비싼거 먹을래? / external 노드는 스타벅스, 홍콩반점

Properities of Proper Binary Trees

  • proper binay tree 의 특성

n : 총 노드의 수( internal 과 external 노드의 수를 합친것)
e : external 노드의 수
i : internal 노드의 수
h : 트리의 높이

proper 이진트리의 높이h 의 범위

  • log2n <= h <= X
    • X : 입력개수
    • 그 이진트리의 최댓값은 X개가 된다. (데이터를 internal 노드에만 저장했을때)
    • 최소는 log2X 정도가 된다.
      ( 입력 개수로 i를 주는 경우가 많다 )
  1. e = i + 1

    • internal 와 external는 개수가 1개 차이난다
    • 하나의 internal을 추가하기 위해선 external 노드를 제거하거나, 새로운 external 노드를 추가해야 하기때문
  2. n = e + i

  3. n = 2e-1

    • i = e-1 이므로, n=e+i 에서 i에다 e-1을 대입한 결과
  4. n = 2i+1

    • 3번을 i에 대해서 풀어쓴거임
  5. h <= i

    • 트리를 가장 높게 만들면, 높이는 internal 노드의 개수이다.
    • 최대로 internal 노드의 개수(= 최대 조상의 개수) 로 만들 수 있다.
    • 만들 수 있는 다양한 조합의 트리중에서, 자기 조상중에 internal 노드가 가장 많은 트리
  1. h <= (n-1) / 2

    • 4번을 변형시키면 i = (n-1)/2 이므로, h <= i 에 (n-1) /2 를 대입한 결과이다.
  2. e <= 2^h

  3. h >= log2e

    • complete binary tree 로 구현했을 때가 트리의 높이가 가장 낮다.
    • ex) interanl 노드가 15개일때(=external 노드가 16개일때) 만들 수 있는 트리의 최소 높이는 log2e = log216 으로, 높이 4가 된다.
  1. h >= log2(n+1) - 1
  • 3번에서 n=2e-1 를 변형시키면 e=(n+1)/ 2 이므로,
    8번식 h >= log2e 의 e의 값에다 e=(n+1)/ 2 를 대입시킨 결과

BinaryTree ADT

메소드

  • 트리의 모든 메소드를 상속받음

  • position p.left()

  • position p.right()

    • 어떤 노드의 position(주소값)이 p라면, 왼쪽 자식과 오른쪽 자식를 리턴받을 수 있다.
    • 즉 이터레이터(position) 을 이용해서 왼쪽,오른쪽 자식의 positiond을 리턴받을 수 있다.
    • 노드형 포인터를 position으로 한다면 왼쪽과 오른쪽 자식의 주소값을 리턴 받을 수 있다는 것
  • 트리에서 하던 update 메소드를 이진트리에서도 가능


이진트리 구현 - linked structure로 구현

필드

  • 데이터 필드
  • parent 필드 (parent 노드형 포인터)
  • left child 필드 (left child 노드형 포인터)
  • right child 필드 (right child 노드형 포인터)

그림 분석

노드C

  • data = C
  • parent = D (노드 D의 position, 즉 주소를 저장)
  • left child = NULL;
  • right child = NULL;

Inorder Traversal(중위 순회)

  • 이진트리는 전위순회와 후위순회는 몰론, 중위 순회까지 가능하다.
  • 중위순회 : 자신 노드의 작업을 "중간" 에 처리하는 것

    처리순서
    1) 왼쪽에 Sub tree가 있다면, 왼쪽에 대해서 다 작업하고
    2) 자신을 작업하고
    3) 오른쪽 Sub tree에 대해 작업을 한다.
    => 왼쪽으로 계속 파고들다가 더이상 subtree가 없다면 현재 자기 트리를 처리하고 리턴

Algorithm inOrder(v)
  if ㄱv.isExternal()    // v가 external 노드가 아니라면 == 왼쪽자식이나 오른쪽 자식이 존재한다는 뜻
    inOrder(v.left())     // 왼쪽 subtree 대해서 먼저 중위순회를 해라!
  visit(v)                // 그러고 나서 나를 작업해라!
  if ㄱv.isExternal()         // 그러고 오른쪽에 대해서 중위순회를 해라
    inOrder(v.right())        

  • 활용분야 : 이진트리를 좌표 평면에 겹치지 않게 그리기

v의 좌표 ( x(v), y(v) ) 는 v의 inorder traversal 을 했을때 처리되는 순서가 x좌표가 되고, y좌표는 v의 깊이로 해주면 된다.

주의!) 좌표는 1부터 시작한다. 0부터가 아니다!!(감점요소)

x(v) = inorder rank of v
y(v) = depth of v

how 그리기?

  • 각 노드는 (x좌표, y좌표) 값이 겹치는 것이 없도록 할것.
    (당연히 각 노드의 x좌표값이 중위순회의 처리 순서를 넣어주므로 겹치지 않는다.)
profile
블로그 이전 : https://haon.blog

0개의 댓글