레드블랙 트리(Red-black tree)
이진검색트리는 저장과 검색에 평균 Θ()시간이 소요되지만 운이 나쁘면 트리의 모양이 균형을 잘 이루지 못한다. 균형이 많이 깨지면 Θ(n)에 근접한 시간이 소요될 수도 있다. 그래서 고안해 낸 것이 균형잡힌 이진검색트리이다. 균형잡힌 이진검색트리는 최악의 경우에도 이진트리의 균형이 잘 맞도록 유지한다. 균형잡힌 이진검색트리로 대표적인 것은 레드블랙트리와 AVL트리다. 레드블랙 트리는 자가균형이진탐색 트리(self-balancing binary search tree)로써, 대표적으로 연관배열(associative array) 등을 구현하는데 쓰이는 자료구조이다. 레드-블랙 트리는 복잡한 자료구조이지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다. 트리에 n개의 원소가 있을때..
이진트리의 순회 (Binary Tree Traversal)
이진검색트리같은 이진트리(Binary tree) 구조의 자료구조에서 검색, 출력 등의 이유로 전체 노드들을 방문(visit)하는 것을 순회(traversal)이라고 합니다. 아시다 싶이 이진트리의 구조는 최상위에 루트(root)가 존재하고 좌측에는 왼쪽 서브트리가 , 오른쪽에는 오른쪽 서브트리의 모양을 갖습니다. 대표적인 이진트리 순회 방법에 3가지의 방법이 있습니다. 루트의 방문 순서에 따라 구분이 됩니다. 1. 전위 순회 (Preorder Traversal)Root -> Left Tree -> Right Tree ( 루트를 제일 처음에 방문 )2. 중위 순회 (Inorder Traversal)Left Tree -> Root -> Right Tree ( 루트를 중간에 방문 )3. 후위 순회 (Posto..