240315_RBtree_고재원

[icu222]

1. 트리의 특징에 대해 아는만큼 설명해주세요

• 노드와 링크로 구성
• 사이클이 없다
• 링크의 방향이 없다
• 노드-링크 = 1이다.

1-1. 이진 트리는 어떻게 만드나요?

입력 값이 주어지면 leaf에 도달 할 때 까지
자신보다 큰 값은 오른쪽으로, 작은 값은 왼쪽으로 내려보냅니다.

2. 리스트나 배열에 비해 이진 트리는 어떤 이점이 있나요?

값을 검색 할 때 리스트나 배열은 O(n)의 속도인 반면, 이진 트리는 O(logN)입니다.

3. 그렇다면 이진 트리의 단점은 무엇이고, 이를 해결하기 위해 어떻게 해야 하나요?

트리에 값이 편향되게 입력되면 이진 트리가 아닌 리스트처럼 구성 될 수 있으므로 최악의 경우 검색 시 O(n)의 속도를 가집니다.
따라서 트리가 편향되지 않도록 스스로 균형을 잡는 알고리즘을 사용해야 합니다.
(대충 AVL tree 내용 들어가면 정답)

4. red-black tree의 5가지 특징이 무엇인지 써 보세용

1. 모든 노드는 red or black이다.
2. root 노드는 black이다.
3. 모든 nil, 즉 leaf노드는 black이다.
4. red노드의 자식은 무조건 black이다.
5. 어느 노드에서 자손 NIL노드까지의 모든 경로에서 만나는 black node의 수는 같다.

(선택) 5. 발표 자료를 보고 25를 넣어봅시다