muntari Log muntari Log

이진 탐색 트리와 해시 테이블 해시 테이블로 구현하는 딕셔너리와 세트 자료형을 이진 탐색 트리로 구현할 수 있다. 노드 인스턴스를 딕셔너리와 세트의 인스턴스로 지정하여 구현할 수 있다고 한다. 먼저 왜 이진 탐색 트리로 딕셔너리와 세트 자료형을 구현해서 사용하는 이유를 알아보자. 딕셔너리와 세트 자료형은 파이썬 내부적으로 해시 테이블로 구현되어 있다.(해시 테이블 포스팅 참고) 굳이 이진 탐색 트리로 구현하는 이유는 뭘까? 해시 테이블의 경우 데이터의 순서 관계를 저장하지 않는 자료구조이다. 반면에, 이진 탐색 트리의 경우 데이터 사이에 순서를 저장하는 역할 하는 자료구조이며 in-order 방식으로 노드를 순회하면 트리 안에 있는 데이터를 순차적으로 출력할 수 있다. 결국, 세트의 데이터나 딕셔너리의 ..

이진 탐색 트리 트리의 일종으로 이진 트리이면서 이진 탐색 트리의 속성을 만족하는 트리를 이진 탐색 트리라고 부른다. 영어로는 Binary Search Tree 라고 부른다. 이진 탐색 트리를 사용하면 저장한 데이터를 쉽게 찾아 올 수 있다. 이진 트리는 각 노드가 최대 2개의 자식 노드만 가질 수 있는 트리를 말한다. 이진 트리에서는 모든 노드가 2개, 1개, 0개의 자식 노드만 가지고 있다. 여기서 이진 탐색 트리의 속성은 아래와 같다. 1. 특정 노드를 기준으로, 특정 노드의 왼쪽 부분 트리에 있는 모든 노드는 특정 노드의 데이터보다 작아야 한다. 2. 특정 노드를 기준으로, 특정 노드의 오른쪽 부분 트리에 있는 모든 노드는 특정 노드의 데이터보다 커야 한다. 루트 노드가 아닌 모든 루트에 적용되는..