레드-블랙 트리에 대한 설명으로 옳지 않은 것은? (단, 노드의 개수는… | [7급 국가직 자료구조론] 11년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 11년 1회차
레드-블랙 트리에 대한 설명으로 옳지 않은 것은? (단, 노드의 개수는 n이다)
1
이진 탐색 트리의 일종이며, 각 노드는 레드 또는 블랙의 색상을 부여받는다.
2
부모-자식 관계에 있는 두 노드는 동일한 색을 가져서는 안된다.
3
레드-블랙 트리의 높이는 항상 O(log⁡n)O(\log n)이 된다.
4
삽입과 삭제 연산의 시간 복잡도는 O(log⁡n)O(\log n)이다.
해설

레드-블랙 트리에서 금지되는 것은 레드 노드의 자식이 레드인 경우뿐이므로, 부모와 자식이 같은 색이면 안 된다는 설명이 옳지 않다.

블랙 부모 아래 블랙 자식은 허용되며, 루트에서 각 리프까지 경로의 블랙 노드 수가 같다는 조건으로 균형을 유지한다.

  • 레드-블랙 트리는 각 노드에 레드 또는 블랙 색을 부여한 이진 탐색 트리이다.
  • 색 규칙 덕분에 최장 경로가 최단 경로의 2배를 넘지 않아 높이가 로그 수준으로 유지된다.
  • 높이가 로그 수준이므로 삽입·삭제(재색칠·회전 포함)도 로그 시간에 끝난다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 11년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기