반응형 분류 전체보기340 [알고리즘] Tree - 레드 블랙 트리(Red Black Tree) - 2 Tree - 레드 블랙 트리(Red Black Tree) - 2 이어서 레드 블랙 트리의 insert연산에 대해 알아보자순서는 다음과 같다.1) BST에서 처럼 노드를 insert한다.2) 새로운 노드 z를 red 노드로 한다.3) RB-Insert-fixup을 호출한다. 12345678910111213141516171819RB-INSERT(T,z){ y 2017. 4. 19. [알고리즘] Tree - 레드 블랙 트리(Red Black Tree) - 1 Tree - 레드 블랙 트리(Red Black Tree) - 1 앞서 본 이진 탐색 트리의 기본연산 3가지(Insert, Search, Delete)가트리의 높이에 비례하는 시간복잡도를 가지고 있었다.이때, 극단적으로 비대칭 적이며 높이가 높은 트리에서는 그 효율이 높지 않다. 따라서 이진 탐색 트리의 구조를 유지하며 안정성도 살리는 트리가 필요해졌다.이 들 중 하나가 레드 블랙 트리이다. 레드 블랙 트리는 이진 탐색 트리의 일종이다.이진 탐색 트리에서 Insert와 Delete 알고리즘을 적절하게 수정하여이진 탐색 트리임에도 불구하고 트리의 높이에 상관없이 O(logN)의 시간복잡도를 유지해준다. 레드 블랙 트리의 형태는 다음과 같다.1) 각 노드는 하나의 키(key), 왼쪽 자식 노드, 오른쪽 자식 .. 2017. 4. 19. [알고리즘] Tree - 이진 검색 트리 - 3 Tree - 이진 검색 트리 - 3 이어서 delete 연산이다.delete가 3개의 연산중에 가장 복잡한데, 경우에 따라 연산이 다르기 때문이다. 첫번째는 자식이 없을 때이다.자식이 없을 때는 노드를 그냥 삭제한다. 두번째는 하나의 자식이 있는 경우이다.이 경우는 링크드 리스트에서 가운데 값을 하나 삭제하는 것과 비슷하므로간단하게 처리할 수 있다.7을 삭제하고 노드 6의 포인터를 13을 가리키도록 해주면 된다. 마지막으로 자식을 둘인 노드를 삭제하는 경우이다.이것이 delete 연산의 가장 복잡한 경우이다 노드 13을 삭제하는 경우, 13을 그냥 없애 버리면 자식 노드의 부모가 없어지므로 노드 13의 저장된 데이터(13)만 삭제한다. 이후에 없어진 데이터의 successor를 삭제된 부분으로 옮겨온다... 2017. 4. 19. [알고리즘] Tree - 이진 검색 트리 - 2 Tree - 이진 검색 트리 - 2 12345TREE-MINIMUM(x){ while left(x) != null do x 2017. 4. 19. 이전 1 ··· 54 55 56 57 58 59 60 ··· 85 다음 반응형
