본문 바로가기

이진탐색트리2

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 다음

티스토리툴바