이진 검색 트리의 경우 인서트시 오름차순이나 내림차순으로 넣으면 우측자식으로만 혹은 좌측자식으로만 계속 자라는 편향적인 구조가 되버린다. 이것은 트리의 깊이가 집어 넣는 개수만큼 계속 깊어지므로 결국 순차검색(Sequence Search)과 다름없는 최악의 결과가 된다. 순차적으로 집어넣는 경우는 일상적으로도 아주 많을 것이다. 그러므로 이런 삽입과 삭제시 밸런스를 맞추는 알고리즘에 대한 연구가 많이 진행되었다. 레드블랙트리는 밸런스 트리의 대명사인 B트리에서 차원이 3인 경우와 이론적 구조가 같다. 다만 이진트리는 각 노드에 요소가 한개밖에 들어갈 수 없으므로 이를 레드와 블랙이라는 논리적인 요소를 도입함으로써 이진트리의 형식으로 구현한 것이다. 실제로도 B트리나 2-3-4트리 다음에 등장한 이론으로 ..

위 파일은 인터넷서 얻은 도식화 파일이다. 그림으로 설명이 참 깔끔하게 잘 된듯 하다. 참조... http://swblog.net/entry/B-Tree B트리의 처리 방식은 제각각인 듯 하다. B트리의 원칙만 잘 지키면 되는 듯 하다. 삽입의 경우 좀 특이하게 처리했던 경우는(이재규 알고리즘 강좌) 일단 위에서부터 아예 포화상태에 놓인 경우(5차원시 노드에 5개 요소가 있는경우) 먼저 분할시키면서 아래로 내려와서 마침내 들어갈 자리를 찾으면 해당 노드에 요소를 삽입하는 방식이다. 이때문에 해당 노드에서 분할시에 부모가 오버플로우될 상황은 없다.(부모노드 요소의 갯수는 모두 4개 이하이므로) 다른 방식은 위 도식화에서 표현하듯이 저질러놓고 수습하는 방식인 데 이게 일반적인 경우인 듯 하다. 일단 해당 값..