본문 바로가기

분류 전체보기137

12-2강. 레드블랙트리 (3) RB-DELETE(T, z) // T: Binary Search Tree, z : 삭제할 노드 if left[z] == nil[T] or right[z] == nil[T]// 자식이 없거나, 자식이 하나거나 then y 2020. 11. 22.

12-1강. 레드블랙트리(1) 문제 상황 : 현실세계에서는 완벽하게 정렬된 Binary Search Tree는 찾기 힘들다. 오른쪽으로 극단적으로 치우친 경우가 존재할 수 있다. 보완 방법 : 레드블랙트리(Red-Black Tree)는 이를 보완하기 위해 등장했다. 완벽하게 트리의 균형을 맞출 수는 없으나, 어느정도 보완을 가능하게 한다. INSERT, DELETE 알고리즘을 적절하게 수정했다. 레드블랙트리 - 이진탐색트리의 일종 - 균형 잡힌 트리 : 높이가 O(log2n) - SEARCH, INSERT, DELETE 연산을 최악의 경우에도 O(log2n) 시간에 지원한다. - 각 노드는 하나의 키(key), 왼쪽자식(left), 오른쪽 자식(right), 그리고 부모노드(p)의 주소를 저장한다. - 자식노드가 존재하지 않을 경우,.. 2020. 11. 17.

11-3강. 이진검색트리 (Binary Search Tree) 지난 강의 공부 내용... 이진검색트리의 탐색, 삽입 이진검색트리/이진탐색트리의 삭제 Case 1 : 자식노드가 없는 경우 -> 해당 노드를 그냥 삭제한다. Case 2 : 자식노드가 1개인 경우 -> 자신의 자식노드를 원래 자신의 위치로 보낸다. Case 3 : 자식노드가 2개인 경우 -> 해당 노드의 자리는 그대로 두고, 데이터만 삭제한다. 그리고 해당 노드와 가자아 가까운 값인 다른 노드를 해당 자리로 가져 온다. 그 다른 노드는 삭제하려는 노드의 successor이다. 삭제하려는 노드의 successor는 최대 1개의 자식노드를 가진다. TREE-DELETE(T, z)// z : 삭제할 노드 { if left[z] == null or right[z] == null then y 2020. 11. 15.

제11-1강. 이진검색트리(Binary Search Tree) 이진검색트리(Binary Search Tree) - 여러 개의 키(key)를 저장 - 다음과 같은 연산들을 지원하는 자료구조 INSERT - 새로운 키의 삽입 SEARTCH - 키 탐색 DELETE - 키의 삭제 ex) 심볼테이블 search insert delete 배열 정렬된 경우 O(logn) O(n) O(n) 정렬되지 않은 경우 O(n) O(1) O(1) 연결리스트 정렬된 경우 O(n) O(n) O(1) 정렬되지 않은 경우 O(n) O(1) O(1) 다양한 방법들 - 정렬된, 혹은 정렬되지 않은 배열 혹은 연결리스트를 사용할 경우 INSERT, SEARCH, DELETE 중 적어도 하나는 O(n) - 이진탐색트리(Binary Search Tree), 레드-블랙트리(red-black tree), A.. 2020. 11. 10.

이전 1 ··· 30 31 32 33 34 35 다음

티스토리툴바