이진 탐색 트리 (Binary Search Tree)
딕셔너리(Dictionary)는 페어(Pair)의 모음으로, 각 페어는 Key값과 관련된 다른 값들로 이루어져 있다. 일반적인 딕셔너리 구조는 실제로는 그렇지 않음에도 불구하고 중복된 키값이 없다 가정하지만, 이진 탐색 트리에서는 이러한 가정 없이 쉽게 중복 키값에 대해 확장할 수 있는 자료구조이다.
정의
이진 탐색 트리는 이진 트리의 한 종류로써, 다음 조건들을 만족하는 자료구조이다.
① 각 노드는 구분되는 하나의 키값을 갖는다.
② 왼쪽 서브트리의 모든 키값들은 root의 키값보다 작다.
③ 오른쪽 서브트리의 모든 키값들은 root의 키값보다 크다.
④ 왼쪽, 오른쪽 서브트리 각각 또한 이진 탐색 트리이다.
탐색 (Search)
삽입 (Insertion)
삭제 (Deletion)
※ 본 게시글은 『Fundamentals of Data Structures in C』 를 참고하여 작성되었습니다.
'자료구조' 카테고리의 다른 글
[자료구조] 트라이 (Trie) (2) | 2020.12.21 |
---|---|
[자료구조] Red-Black 트리 (0) | 2020.11.21 |
[자료구조] AVL 트리 (0) | 2020.11.20 |
[자료구조] 힙 (Heap) (0) | 2020.11.20 |