Data Structure - Red Black Tree (작업중, 알고리즘으로 이전할 것)

Binary Search Tree? 

          레드 블랙 트리를 배우기 전 알아야할 자료구조. 이진 검색 트리는 저장과 검색에 평균 O(LogN) , 최악 O(N) 의 

          비교적 불완전한 구조를 가진다. 이 불 완전성을 해결하기 위해 고안된 것이 균형잡힌 이진트리 이다.

          균형잡힌 이진트리로 대표적인 것은 레드 블랙 트리, AVL 트리이다. 여기서는 레드 블랙 트리를 다룬다.

 

         

임시로 그려놓은 트리구조

          이 Tree 에서 중위 순회(왼쪽자식 -> 부모 -> 오른쪽자식)를 할 때, 다음과 같은 Key를 얻는다.

          결과 : 20 -> 30 -> 40 -> 50 -> 60 -> 80

          이를 다시 트리에 넣게 되면, 다음과 같은 최악의 구조가 나온다.

탐색시간 O(N)의 최악의 트리

          이 Depth 를 Balance 있게 잡아줄 트리라고 생각하면 된다.

Red Black Tree ? 

          기본은 Binary Search Tree 에 국한되며, 최악의 경우를 맞이하는 것을 방지하기 위한 트리 

          탐색시간이 O(Log N)에 수렴하며, BST에서 여러 조건들이 추가된 것으로 판단된다.

 

Red Black Conditions ? 

          1. 루트 노드는 블랙이다.

          2. 모든 리프는 블랙이다.

          3. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.

          4. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.

 

 

 

 

 

여기에 설명이 너무 잘되어있다.. 포스팅은 자료를 더 구한다음에 더 추가해서 하겠습니다.

zeddios.tistory.com/237

알고리즘 ) Red-Black Tree