WHAT WE TAGS binarysearchtree LIST
이진 탐색 트리가 다른 자료 구조들에 비해서 실제로 얼마나 효율적인지 보자. 비교 이진 탐색 트리와 용도가 비슷한 자료 구조가 뭐가 있었는지 생각해보자. 일단 이진 탐색 트리를 사용하는 가장 대표적인 예시는 추상 자료형, 세트(set)와 딕셔너리(dictionary)를 구현하는 것이다. 해시 테이블을 사용해도 두 추상 자료형을 구현할 수 있었던
이진 탐색 트리를 이용하면 추상 자료형 딕셔너리를 구현할 수 있다고 했다. 딕셔너리 (또는 맵)는 key - value 데이터 쌍을 찾고, 저장하고, 지울 수 있게 해주는 추상 자료형이다. 이진 탐색 트리를 사용해서 어떻게 딕셔너리를 구현할 수 있는지 알아보자. 이진 탐색 트리 Node 딕셔너리용 이진 탐색 트리 Node class
트리의 높이가 h 라고 할 때, 이진 탐색의 가장 기본적인 연산들: 탐색, 삽입, 삭제의 시간 복잡도는 모두 O(h) 다. 따라서 이진 탐색 트리 는 높이가 낮을수록 여러 연산을 하기에 효율적이라는 것을 알 수 있다. 이번에는 이진 탐색 트리의 높이, h 에 대해서 좀 더 깊이 알아보자. 이진 탐색 트리
이진 탐색 트리 삭제 연산 시간 복잡도 삭제 연산의 각 경우들의 시간 복잡도들에 대해서 생각해보자. 탐색 일단 삭제 연산은 공통적으로 삭제하려는 데이터를 갖는 Node 를 탐색해야 한다. 이진 탐색 트리의 높이를 h 라고 했을 때, 탐색 연산은 O(h)의 시간 복잡도가 걸린다. 데이터를 삭제할 때의
실습과제 이진 탐색 트리 삭제 연산에서 마지막 경우: 두 개의 자식이 모두 있는 Node를 삭제하는 경우를 코드로 구현해 보자. 세 번째 경우에 해야할 작업을 순서대로 나타내면 아래와 같다. 지우려는 Node의 successor를 받아온다. (find_min 메소드 활용). 삭제하려는 Node 데이터에 successor의 데이터를 저장한다. successor Node를 삭제한다. 이렇게 해주면 됐었다.
경우 3) 삭제하려는 데이터의 Node 가 두개의 자식이 있을 때 만약 아래의 사진에서 2개의 자식이 있는 12 를 지우고 싶다고 하자. 자식이 2개가 있는 Node 를 삭제하려면 다른 Node 가 자리를 메꿔줘야한다. 그 자리에 들어갈 Node 를 어떻게 정하는지 알아보자.
실습과제 이진 탐색 트리 삭제 연산 중 두 번째 경우: 하나의 자식만 있는 Node를 삭제하는 경우를 구현해 볼 것이다. 이 경우는 “삭제하는 Node의 위치를 자식 Node가 대신 차지한다”를 해주기만 하면 된다. 사실 생각보다 많은 작업들을 해줘야 한다. 코드를 쓰면서 삭제하려는 Node가 root Node인지, 삭제하려는 Node가 부모의 왼쪽 자식인지
실습과제 이진 탐색 트리 삭제 연산 중 첫 번째 경우: leaf Node를 삭제하는 경우를 코드로 구현해 보자 leaf Node를 삭제하는 알고리즘을 일반화하면 이렇게 표현할 수 있다. 먼저 search 메소드를 사용해서 삭제하려는 데이터의 Node를 받아온다. 삭제하려는 Node가 부모 Node의 왼쪽 자식이면 부모의 왼쪽 자식을 None으로 바꿔준다 삭제하려는 Node가 부모
이진 탐색 트리 에서는 데이터를 삽입할 때에 비해 여러가지 상황을 고려해야한다. 삭제하려는 데이터를 갖는 Node 를 먼저 찾아야함 만약 7을 삭제해야 한다고 가정하자 그러면 이 7 의 데이터를 가지고 있는 Node 를 찾아야 한다. 이 경우에서는 탐색 연산을 이용하여 찾으면 된다.
실습과제 이번에는 이진 탐색 트리의 색다른 메서드를 구현해 볼 것이다. 이진 탐색 트리에서 가장 작은 Node를 찾아주는 메소드다. 정적 메소드 find_min는 파라미터로 node를 받는다. node를 뿌리로 갖는 부분 트리 안에서 가장 작은 Node를 리턴해준다. 이게 무슨 말인지 조금 헷갈리실 수 있다. 예를 들어서 이런 이진 탐색 트리가 있다고 합시다.