jungle RB Tree 레드블랙트리 자료구조 data structure 그래프 graph 트리 tree binary tree 이진트리 이진검색트리 binary search tree

레드 블랙 트리 이해하기

정글 되돌아보기

Red-Black Tree

개념

레드-블랙 트리. 이진 검색 트리의 한 종류이다. 그렇다면 트리는 뭔지, 이진 검색트리는 또 뭔지, 레드-블랙 트리는 어떤 특별한점이 있는지부터 알아보겠다.

자료구조(data structure)

개발자 공부를 하면서 수도 없이 들어봤을 자료구조. 지금 자료구조가 뭐냐고 묻는다면 나는

“list, set, deque, queue, stack 같은 것들처럼 데이터들이 어떤 형태와 관계로 들어있는지를 나타내는 것입니다.”라고 대답할 것 같다.

면접이라 생각하고 머릿속에 떠오르는걸 그대로 받아적었는데 생각보다 나쁘지 않은데? 그럼 정확한 정의부터 살펴보자.

INTRODUCTION TO ALGORITHMS THIRD EDITION 책에는

자료를 편리하게 접근하고 변경하기 위해 자료를 저장하거나 조직하는 방법

이라고 나와있다. 위키피디아를 살펴보자.

In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data.

토익 800점대의 해석으로는 “ 컴퓨터 과학에서, 자료구조는 자료 조직, 관리, 저장 형태인데 보통 자료에 효율적인 접근을 위해 선택된다.” 라는 뜻이다.

위 둘을 토대로 나의 정의는

자료구조는 자료에 효율적으로 다루기 위해 선택하는 자료 조직, 관리, 저장 형태

라고 하겠다.

그럼 예시로는 뭐가 있을까? 좀 들어본 애들만 골라서 말하자면

array, linked list(우리가 list라 하는 그 친구), record(tuple, struct라고도 함), hash table, graph(우리가 봐야할것) 등 이 있다.

각각의 자세한 내용은 추후에 알아보고 우선 graph부터 보자.

그래프(graph)

위키피디아의 정의는 아래와 같다.

In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from the field of graph theory within mathematics.

” 컴퓨터 과학에서, 그래프는 추상적인 자료 종류인데 수학의 그래프 이론 분야에서 가져온 무방향 그래프와 방향 그래프 개념을 수행하기 위해 의도된 것이다.”라는 말로 해석된다. 사실 간접/직접으로 해석했는데 찾아보니 무방향/방향 이였다.

chatGPT4에게 물어본 결과는 다음과 같다.

객체 간의 이진관계를 표현하는 자료구조로 node(노드), vertex(정점)라 불리는 개체들과 이들을 연결하는 edge(간선), link(링크)로 구성된다. weight(가중치)를 가질수 있는데 일반적으로 두 노드 사이의 거리, 비용, 용량등을 나타낸다.

라고 한다. 방향 그래프와 무방향 그래프는 각각

“간선에 방향성이 있는 그래프로 A->B 경로는 있지만 B->A 경로는 없을 수 있다.”

“간선에 방향성이 없는 그래프로 A->B 경로가 있다면 B->A 경로는 반드시 있다.”

라고 말해주었다. 정리해보자면

그래프는 node 같은 개체들끼리 edge로 이어져 있는지 아닌지를 표현하는 자료구조

방향,무방향이 있으며 출발지와 도착지가 바뀌는게 영향이 있는지를 나타냄

weight의 개념도 존재함

라고 받아들이겠다.

그래프의 예시는 Tree(트리), Subgraph(서브그래프), Complete Graph(완전 그래프), Multigraph(다중 그래프), Biparitite Graph(이분 그래프), Weighted Graph(가중치 그래프), Cyclic Graph(순환 그래프), Acyclic Graph(비순환 그래프)등이 있다고 한다. 역시 나중에 따로 알아봐야겠다.

트리 (tree)

드디어 트리의 개념에 도달했다. 트리의 정의부터 위키피디아에서 살펴보자

In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes.

” 컴퓨터 과학에서, 트리는 널리 사용되는 추상적인 자료 종류인데, 연결된 노드들의 묶음이 있는 계층적 트리 구조를 나타낸다.” 로 읽혔다.

tree를 정의하면서 tree를 사용하다니 치사하다.

친구비를 결제한 내 친구(GPT-4)에게 물어보자.

다음 조건을 충족하는 연결 그래프(Connected Graph)입니다.

  1. 사이클(Cycle)이 없는 그래프입니다. 즉, 어떤 노드를 출발점으로 해서 이동하면서 자기 자신으로 돌아오는 경로가 없어야 합니다.
  2. 어떤 두 노드도 정확히 한 가지 방법으로만 연결됩니다. 다시 말해 임의의 두 노드를 선택하면 그 두 노드를 연결하는 경로는 단 하나뿐입니다.

트리에는 ‘루트(root)’라고 불리는 특별한 노드가 있는데, 이는 트리의 시작점이자 모든 다른 노드들의 조상입니다. 이러한 특성 때문에 트리는 ‘부모-자식’ 관계를 가진 노드들로 구성된 계층적 구조를 나타내는 데 종종 사용됩니다.

루트에서 어떤 노드로 가는 경로는 한 가지뿐이고, 그 경로는 그 노드의 ‘조상’ 노드들을 모두 통과합니다. 반대로, 어떤 노드의 ‘후손’ 노드들은 그 노드를 조상으로 가지는 모든 노드들을 의미합니다.

역시 친구가 최고다. 그럼 다음과 같이 정리해보겠다.

  1. 맨 위 꼭대기에는 **루트**라는 노드가 존재한다.
  2. 노드간에는 딱 **1개**로만 연결되어 있다.
  3. 루트에 연결된 다른 노드들은 루트의 자식노드이다. 바꿔 말하면 이 노드들의 부모는 루트이다.
  4. 후손과 조상의 의미랑 헷갈리지 말자. 할아버지는 부모는 아니지만 조상은 맞다.
  5. 부모의 부모의 부모의 ... 로 찾아가면 결국 루트노드가 나온다. 호적(?)과 가계도마냥 계층이 있다.
  6. 아무 두 노드를 고르고 둘의 연결 경로는 단 하나다.

이렇게 요약해보았다. 이러니 크리스마스 트리처럼 삼각형 모양이 된다.

사실 우리의 목적지는 Red-Black Tree임을 잊지 말자. 그러기 위해 이진검색트리부터 알아보자

이진 검색 트리(binary search tree)

또키피디아로 가보겠다.

In computer science, a binary search tree(BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node’s left subtree and less the ones in its right subtree.

말이 참 길다. 해석해보자.

” 컴퓨터 과학에서, 이진 검색트리는 순서이진트리, 정렬이진트리라고도 불리는데, root가 있는 이진 트리 자료구조이며 왼쪽 서브트리의 key보다는 더 크고 오른쪽 서브트리의 key 보다는 더 작은 각 내부 노드들의 key를 가진다. “

영어가 딸린게 아니라 한국말이 딸려서 번역이 힘들다. 문장을 나눠서 말하자면

  1. 이진 검색트리는 root가 있다.
  2. 모든 노드들은 왼쪽의 서브트리들의 모든 key들 보다 더크고 오른쪽의 서브트리들의 key들보다 더작은 key를 가진다.

라고 이해하였다.

그럼 이진트리는 뭐지? 친구(GPT4)에게 물었다.

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 형태의 자료구조입니다. 자식 노드는 각각 ‘왼쪽 자식’과 ‘오른쪽 자식’으로 구분됩니다.

따라서, 이진 트리의 각 노드는 최대 세 개의 참조를 가지게 됩니다: 하나는 값(value) 또는 키(key), 다른 두 개는 왼쪽 자식(left child)과 오른쪽 자식(right child) 노드에 대한 참조입니다.

이진법에도 쓰이는 ‘이진’이라는 말이 0 혹은 1, 둘 이라는 뜻이니까 자식 노드가 두개뿐인 트리를 말한다.

계속해서 친구찬스를 사용하겠다.

특별한 속성을 가진 노드 기반의 이진 트리 자료 구조입니다.

이진 검색 트리의 각 노드는 키(key), 값(value), 그리고 최대 두 개의 자식 노드에 대한 참조(일반적으로 ‘왼쪽’과 ‘오른쪽’ 자식으로 불림)로 구성됩니다. 이진 검색 트리는 다음의 속성을 만족해야 합니다:

  1. 각 노드의 키는 그 노드의 왼쪽 하위 트리에 있는 모든 노드의 키보다 크거나 같아야 합니다.
  2. 각 노드의 키는 그 노드의 오른쪽 하위 트리에 있는 모든 노드의 키보다 작거나 같아야 합니다.

이러한 속성 덕분에, 이진 검색 트리에서 어떤 특정 키를 탐색하는 것은 평균적으로 상당히 빠르며, 탐색 시간은 트리의 높이에 비례합니다.

깔끔하다. 역시 문장이 길어서 좋을게 없다. 정리해보자

  1. 이진트리란 트리 중 자식의 수가 최대 2개인 트리를 말하고 value나 key값, left child(왼쪽 자식), right child(오른쪽 자식)으로 참조된다.
  2. 이 이진트리 중 왼쪽자식이 포함된 하위트리에는 key값이 더 작은 노드들만 존재한다.
  3. 이 이진트리 중 오른쪽자식이 포함된 하위트리에는 key값이 더 큰 노드들만 존재한다.

왼쪽자식으로 가면 점점 값이 작아지고, 오른쪽으로 가면 커진다.

이제 진짜 마지막이다

레드블랙 트리(Red-Black Tree)

In computer science, a red–black tree is a specialised binary search tree data structure noted for fast storage and retrieval of ordered information, and a guarantee that operations will complete within a known time.”

” 컴퓨터 과학에서, 레드블랙 트리는 구체화된 이진 검색 트리 자료 구조인데 정리된 정보의 빠른 저장과 복구, 그리고 정해진 시간내 수행을 보장하는 것을 특징으로 한다”

개발 실력이 느는건지 해석실력이 느는건지 잘 모르겠다.

오랜만에 책에서 정의를 찾아보겠다.

레드블랙 트리는 이진 검색 트리로서 각 노드당 한 비트의 추가 기억 공간을 가진다. 이 비트는 노드의 색깔을 나타내는데, 적색(RED)이나 흑색(BLACK)이 될 수 있다. 레드블랙 트리는 루트에서 리프까지의 경로에 나타나는 노도의 색깔을 제한함으로써 그런한 경로 중 어떠한 것도 다른 것보다 두 배 이상 길지 않음을 보장하게 되는데, 이로써 트리는 근사적으로 균형을 이루는 트리가 된다.

다음 조건을 만족하는 이진 검색트리를 레드블랙 트리라고한다.

  1. 모든 노드는 적색이거나 흑색이다.
  2. 루트는 흑색이다.
  3. 모든 리프(NIL)는 흑색이다.
  4. 노드가 적색이면 그 노드의 자식은 모두 흑색이다.
  5. 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.

INTRODUCTION TO ALGORITHMS의 내용이다. 그동안 GPT4(친구)가 말한 것들을 수용했는데 이 책과 비교해봐서 신뢰성을 확보해보겠다.

레드-블랙 트리(Red-Black Tree)는 이진 검색 트리의 한 종류로, 균형이 유지되도록 설계된 트리입니다. 이 트리는 트리의 깊이를 최소화함으로써 효율적인 검색, 삽입, 삭제 연산을 보장합니다.

레드-블랙 트리는 이름에서 알 수 있듯이 각 노드에 색상(빨강 또는 검정)이 부여되며, 트리의 구조가 다음의 특성을 만족하도록 유지됩니다:

  1. 모든 노드는 빨강이나 검정의 색상을 가집니다.
  2. 루트 노드는 항상 검정입니다.
  3. 모든 리프 노드(트리의 끝에 위치한 노드)는 검정입니다.
  4. 빨강 노드의 자식 노드는 모두 검정입니다. 즉, 빨강 노드는 연속되어 등장하지 않습니다.
  5. 각 노드에 대해 그 노드로부터 자손인 모든 리프 노드까지의 경로에는 동일한 개수의 검정 노드가 있습니다.

“레드블랙 트리 정의해줘”라는 질문의 대답이다. 똑같다. 굉장히 믿을만한 친구다.

5번에 대해 조금 더 설명해보겠다. 우선 리프노드는 가장 마지막 밑에 있는 노드들로서 자식노드가 없다.

아무 노드를 선택하면, 그 노드에서 자신의 자손인 리프노드들이 있을 것이다. 그들 중 하나를 정해 어느쪽으로 가면서 만나는 검정 노드가 몇개일지를 세보자.

목적지를 어디로 정하든 자식인 리프노드로 가는동안에는 같은 갯수의 검정노드를 만난다는 뜻이다. 못난 실력이지만 그림을 그려보겠다.

레드블랙트리

(출처 : 위키피디아)

사실

8을 기준으로 잡고 1,6,11의 자식노드이자 리프노드인 NIL 중 어디든 가면서 만나는 검정 노드를 세보자.

2개. 무조건 2개다. 13이든 25든 그 누구를 고르든 성립한다. 왜냐하면

빨강 노드가 리프노드 일수 없음 + 빨강 노드의 자식은 반드시 블랙노드

이 2가지 이유때문인 것같다. 그렇다면 사실 특징이라기보다는 자연스럽게 생긴 규칙이라고 봐야되지 않을까.

하지만 대단한 교수님들이 쓰신 책에서 말하는덴 이유가 있을테니 받아들이겠다.

정리해보겠다.

  1. 레드,블랙은 색깔을 의미한다. 규칙에 맞게 설정되야 한다.
  2. 루트(꼭대기)와 리프 노드(맨 바닥)은 무조건 블랙이다.
  3. 블랙 노드의 자식은 상관없지만 레드 자식의 노드는 모두 블랙이여야 한다.
  4. 어떤 노드든 후손인 리프노드 까지 갈 때 블랙의 수를 세보면 일치한다.

이로써 레드블랙-트리의 정의를 알아봤다.

꼼꼼히 알아다보니 글도 길어지고 시간도 많이 썼다.

내일 혹은 모레가 될 다음에는 이 레드블랙 트리를 수정,삽입,삭제 할때 어떤일이 발생하는지 공부하고 정리하겠다.

출처

  1. https://en.wikipedia.org/wiki/Main_Page

  2. https://chat.openai.com/?model=gpt-4
  3. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 지음, , 문병로, 심규석, 이충세 옮김,The MIT Press, 2014
CATALOG
    remind