Tree

문지원(JiwonMoon)·2022년 6월 11일
0
post-thumbnail

🤔 목적

컴퓨터공학의 기초가 되는 cs지식을 되새기면서 이 후 있을 기술면접을 대비 하고자한다.

Red Black Tree 구조는 연관 배열을 구현하는데 사용한다고 알고 있다. 하지만
사용빈도가 작고 현재의 중요성이 떨어진다는 판단하에 간략히 정리하려고 한다.

트리(Tree) 란?

개념

그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.

즉, 이름에서와 같이 나무의 뿌리형태를 생각하면 이해하기 쉬울꺼 같다.

트리는 스택이나 큐와 같은 선형 구조가 아닌 대표적 비선형 자료구조이다. 또한 계층적 관계를 표현하는 자료구조이다. 이 트리라는 자료구조는 표현에 집중해야한다고 한다.
무엇인가를 저장하고 꺼내야한다는 사고에서 벗어나 트리라는 자료구조를 바라보아야한다.

구성요소

  • 노드(Node) : 트리를 구성하고 있는 각각틔 요소를 의미한다.
  • 간선(Edge): 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다.
  • 루트 노트(Root Node) : 트리구조에서 최상위에 있는 노드를 의미한다.
  • 단말 노드 (Terminal Node, leaf Node) :하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다. (즉, 자식노드가 존재하지 않는경우)
  • 내부노드, 비단말 노드(Internal Node): 단말 노드를 제외한 모든 노드로 루트노드를 포함한다.

Binary Tree (이진 트리) 란?

이진 트리는 모든 노드가 최대 2개의 서브 트리를 가지고 있는 트리로, 서브 트리 또한 모두 이진트리이다.
즉, Branch가 최대 2개인 노드로만 구성되는 트리라는 뜻

루트 노드를 중심으로 두 개의 서브 트리로 나뉘어 진다. 또한 나뉘어진 두 서브 트리도 모두 이진트리어야 한다. 재귀적인 정의라 맞는듯 하면서 이해가 쉽지 않다.
한 가지 덧붙이자면 공집합도 이진 트리로 포함 시켜야한다.
그래야 재귀적 조건을 확인해갔을 떄, leaf node 에 다다랐을 때, 정의가 만족되기 때문이다. 자연스럽게 노드가 하나 뿐인 것도 이진 트리 정의에 만족하게 된다.

또한 트리에서는 각 층별로 숫자를 매겨서 이를 트리의 level(레벨)이라고 한다. 레벨의 값은 0부터 시작하고 따라서 루트 노드의 레벨은 0이다. 그리고 트리의 최고 레벨을 가리켜 해당 트리의 height(높이)라고 한다.

이외에도 Perfect Binary Tree (포화 이진 트리), Complete Binary Tree (완전 이진 트리), Full Binary Tree (정 이진 트리) 가 있다.

모든 레벨이 꽉 찬 이진트리를 가리켜 포화 이진트리라고 한다. 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리를 가리켜 완전 이진트리라고 한다.
모든 노드가 0개 혹은 2개의 자식노드만을 갖는 이진 트리를 가리켜 정 이진 트리라고 하고,
배열로 구성된 Binary Tree는 노드의 개수가 n개이고, root가 0이 아닌 1에서 시작할 때 i번째 노드에 대해서 parent(i) = i/2 , left_child(i) = 2i , right_child(i) = 2i + 1 의 index 값을 갖는다.

트리순회란?

트리 자료구조에 포함된 노드들을 특정한 방법으로 한 번씩 방문하는 방법이다.

이른 통해서 정보를 시각적으로 확인할 수 있다. 위에 있는 이진트리의 이미지에 노드(A,B,C)를 예로 들어보면,

  • 전위 순회: 노드, 왼쪽 자식, 오른쪽 자식 순서로 방문하는 순회 방법이다 (A->B->C)
  • 중위 순회: 왼쪽 자식, 노드, 오른쪽자식 순서로 방문하는 순회 방법이다 (B->A->C)
  • 후위 순회: 왼쪽 자식, 오른쪽 자식, 노드 순서로 방문하는 순회방법이다 (B->C->A)

이진 탐색 트리 (Binary Search Tree, BST)란?

이진 탐색 트리는 위의 이진 트리에 조건이 더해진 것이다 또한 모든 노드가 왼쪽자식노드 < 부모노드 < 오른쪽 자식노드의 순서대로 값이 크다.
그리고 같은 데이터 값을 가지는 노드는 존재하지 않는다( 데이터 중복X )

정리하면 아래와 같다

  • 규칙 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.
  • 규칙 2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.
  • 규칙 3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
  • 규칙 4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

Red Black Tree란?

개념

레드-블랙 트리(Red Black Tree)는 자가 균형 이진 탁색 트리로서, 대표적으로 연관 배열 등을 구현하는 데 쓰이는 자료구조이다.
즉, Red Black Tree는 다음 조건을 만족하는 BST이다.

  1. 각 노드는 Red or Black이라는 색을 갖는다.

  2. Root node의 색은 Black이다.

  3. 각 leaf node(NIL)는 Black이다.

    NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드

  4. 어떤 노드의 색이 red라면 두개의 children의 색은 모두 black이다.

  5. 각 노드에 대해서 노드로부터 descendant leaves 까지의 단순 경로는 모두 같은 수의 black nodes 들을 포함하고 있다. 이를 해당 노드의 Black-Height라고 한다.

위 설명을 보고 감이 쉽게 잡히지 않았지만, 예시를 들어보면 쉽게 이해가능하다

레드- 블랙 트리에 새로운 노드를 삽입할 때 새로운 노드는 항상 빨간색으로 삽입한다.
이렇게 되면 4번 조건에 위배되는 상황이 발생한다.
즉, 빨간색 노드가 연속으로 2번 나타날 수 있다 (=Double Red)

레드 블랙 트리는 이러한 Double Red 문제를 해결하기 위해 2가지 방법을 사용한다.

앞으로 새로 삽입할 노드를 N(New), 부모 노드를 P(Parent), 조상 노드를 G(Grand Parent), 삼촌 노드를 U(Uncle)라고 하자. 
즉, 삼촌 노드는 말 그대로 부모의 형제라고 생각하면 된다. 

Double Red가 발생했을 때 

  • 삼촌 노드가 검은색이라면 -> Restructuring을 수행하면 된다.
  • 삼촌 노드가 빨간색이라면 -> Recoloring을 수행하면 된다.

특징

Binary Search Tree 이므로 BST 의 특징을 모두 갖는다.
Root node 부터 leaf node 까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2 보다 크지 않다. 이러한 상태를 balanced 상태라고 한다.
노드의 child 가 없을 경우 child 를 가리키는 포인터는 NIL 값을 저장한다. 이러한 NIL 들을 leaf node 로 간주한다.
RBT 는 BST 의 삽입, 삭제 연산 과정에서 발생할 수 있는 문제점을 해결하기 위해 만들어진 자료구조이다. 이를 어떻게 해결한 것인가?

삽입

우선 BST 의 특성을 유지하면서 노드를 삽입을 한다. 그리고 삽입된 노드의 색깔을 RED 로 지정한다. Red 로 지정하는 이유는 Black-Height 변경을 최소화하기 위함이다. 삽입 결과 RBT 의 특성 위배(violation)시 노드의 색깔을 조정하고, Black-Height 가 위배되었다면 rotation 을 통해 height 를 조정한다. 이러한 과정을 통해 RBT 의 동일한 height 에 존재하는 internal node 들의 Black-height 가 같아지게 되고 최소 경로와 최대 경로의 크기 비율이 2 미만으로 유지된다.

삭제

삭제도 삽입과 마찬가지로 BST 의 특성을 유지하면서 해당 노드를 삭제한다. 삭제될 노드의 child 의 개수에 따라 rotation 방법이 달라지게 된다. 그리고 만약 지워진 노드의 색깔이 Black 이라면 Black-Height 가 1 감소한 경로에 black node 가 1 개 추가되도록 rotation 하고 노드의 색깔을 조정한다. 지워진 노드의 색깔이 red 라면 Violation 이 발생하지 않으므로 RBT 가 그대로 유지된다.

Java Collection 에서 TreeMap 도 내부적으로 RBT 로 이루어져 있고, HashMap 에서의 Separate Chaining에서도 사용된다. 그만큼 효율이 좋고 중요한 자료구조이다.

삽입/삭제에 대한 자세한 사항과 속성/검색 부분은 아래에 블로그를 참고하면 될것같다.
https://lemonlemon.tistory.com/135

정리

레드-블랙 트리는 연관 배열을 구현하는데 사용하는 자료구조이고,
여러가지 규칙이 달린 까다로운 트리구조 BST로 마무리를 지으려고 한다.
더 상세한 부분은 알고리즘에 관한 문제에 접했을 때 추가할 생각이다.

References (참고 자료)

0개의 댓글