시냅스

이진 탐색 트리, Binary search tree 이진 탐색 트리는 각 노드에는 값이 있다. 값들은 전순서(임의의 원소를 비교할 수 있는 부분 순서 집합)가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지신 노드들로 이뤄진다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이워진다. 이진 탐색 트리는 일반적으로 탐색에서 O(log n)으로 장점을 갖는다. 다만, 편향 트리로 이뤄져있다면 O(n)의 가능성이 있다. 이 경우 red black tree를 이용할 수 있다. 아래에서는 Linked list를 사용한 이진 탐색 트리의 구현을 살펴본다. 구현 생성 삽입 개별 node 삭제 Tree 삭제 생성 typedef struct BinSearchTreeNodeType..