[트리] Tree 2: 이진 검색 트리, 트립

1. 검색 트리 검색 트리는 링크드 리스트나 큐처럼 자료들을 담는 컨테이너지만, 자료들을 일정한 순서에 따라 정렬한 상태로 저장해둔다. 이것은 입력이 주어진 순서에 따라 자료들을 배치하는 리스트나 큐와 다른 속성이다. 이런 속성은 원소의 추가 와 삭제만이 아니라 특정 원소의 존재 여부 확인 등의 다양한 연산을 빠르게 할 수 있다. 이진 검색트리는 특히 아주 널리 사용되기 때문에, 이들의 동작 원리와 장단점은 알아야한다. 대부분 이진 검색트리는 라이브러리에서 제공한다. 2. 이진 검색 트리 이진 트리(binary tree) 란 각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드만을 가질 수 있는 트리를 의미한다. 따라서, 이진 트리는 자식 노드들의 배열 대신 두 개의 포인터 left 와 right를 담는 ..

2021.02.04