생성일: 2021년 11월 12일 오후 5:21

Tree

Binary tree

• 각 노드는 최대 2개의 child 노드를 가질 수 있다.
• 하나의 노드로 가기 위한 길은 단 하나여야 함.

여기서 Height == 4

• Full Tree 일때 특성

  N = 최대 노드의 개수, h = Height

  

  

• Binary Tree 일 때 (full이 아닌 것도 포함)

  💡 $log_2(N+1)<= h<=N$ 설명 : full tree일 때가 height가 가장 작고 노드들을 일렬로 쭉 연결한 구조일 때 height가 가장 크다.

• 그냥 Binary tree에서 search의 Big-O는 O(N) ⇒ 링크드 리스트보다 이점이 없음 ⇒ Binary Searh Tree (BST) 사용

Binary Search Tree (BST)

1. 각 노드는 서로 구별되는 데이터를 가진다 (동일한 데이터가 하나의 트리안에 1개만 있다)
2. 각 데이터(value)들은 크기를 비교할 수 있어야 한다.
3. 기준 노드보다 작은 것들은 left subtree로 큰 것은 right tree로 분리한다.
4. 함수들을 대부분 재귀적으로 구현

Searching in a binary search tree

1. root부터 시작
2. 값을 비교
3. 기준 노드과 같으면 found, leaf node인데 같지 않으면 not found
4. 기준 노드보다 작으면 left subtree에서 searching
5. 기준 노드보다 크면 right subree에서 searching
6. 2번부터의 과정 반복

• 시간 복잡도
  • $O(log_2N)$

Tree의 총 노드 개수 세기 : LengthIs()

• 기준 노드 + left subtree의 노드 개수 + right subtree의 노드 개수
• 위의 식을 이용해 재귀적으로 구현

DeleteItem

• 경우의 수
  1. leaf인 노드를 지우기
  2. 하나의 child를 가지는 노드를 지우기
  3. 두개의 child를 가지는 노드를 지우기
• 1, 2번은 그냥 지우고자 하는 노드를 지우면 된다 (2번의 경우에는 지울려고 하는 노드의 parent와 child를 연결)
• 3번일 경우
  1. left subtree에서 가장 큰 Node의 info를 지우고자 하는 노드의 info로 설정하고 찾아온 가장큰 Node를 다시 찾아서 밑에서 지운다.
  2. right subree에서 가장 큰 Node의 info를 지우고자 하는 노드의 info로 설정하고 찾아온 가장큰 Node를 다시 찾아서 밑에서 지운다.
  • 구현은 1번을 이용했다.

Tree Traversal

• means visiting all the nodes in tree

1. Inorder Traversal
   1. 왼쪽 노드 ⇒ 본인 ⇒ 오른쪽 노드 순서로 방문
   2. 트리 출력 함수에서 사용
2. Postorder Traversal
   1. 왼쪽 노드 ⇒ 오른쪽 노드 ⇒ 본인 순서로 방문
   2. delete 함수에서 사용
3. Preorder Traversal
   1. 본인 ⇒ 왼쪽 노드 ⇒ 오른쪽 노드 순서로 방문
   2. binary tree에서 유용 (not binary search trees), CopyConstructor 함수에서 사용

ResetTree, GetNextItem

• Preorder, Inorder, Postorder 중에 사용자가 선택을하면 그 순서대로 queue에 넣는다.
• GetNextItem에서는 3가지 순서로 넣어진 3개의 queue 중에서 사용자가 선택한 순서에 해당하는 queue에서 dequeue한다.

재귀를 반복문으로 재구현 가능

• FindNode함수를 구현하고 이를 이용해 insert, delete 가능
• FindNode(tree, item, nodePtr, parentPtr); 재귀와 다르게 반복문에서는 이것 처럼 부모 노드를 트래킹 하고 있어야 한다. (재귀에서는 레퍼런스로 받아서 지우거나 삽입할 때 부모 노드와 자동 연결이 가능하지만 반복문에서는 불가능)

Big-O

Array를 이용하여 바이너리 서치 트리 구현하기

각 노드를 어레이에 넣는다 ⇒ 이때 잘보면 각 노드가 가지게 될 어레이의 인덱스 번호에 규칙이 있다.

• left child 인덱스 == parent node 인덱스 번호 * 2 + 1
• right child 인덱스 == parent node 인덱스 번호 * 2 + 2
• parent node 인덱스 == (child node 인덱스 번호 - 1) / 2

다양한 Tree들 정의

• Full Binary Treed : 완전한 삼각형 모양

  
  

• Complete Binary Tree : 오른쪽 마지막 부분이 꽉차지 않은 모양 (왼쪽이 차지 않은 것은 complete Binary Tree가 아니다)