추상 데이터 유형 사전을 구현하려고 하면 노드가 값과 연결됩니다. 사전은 기본적으로 전체 순서에서 가져온 요소여야 하는 키 집합입니다. 각 키와 관련된 추가 정보가 있을 수 있지만 개념적 이해로 이어지지는 않습니다.
사전이 트리를 사용하여 구현된 경우 각 노드는 고유한 키를 보유합니다. 여기에서 트리의 각 노드 u에 대해 모든 키는 u.l입니다. u.l은 u.k보다 엄격하게 작습니다. 그리고 u.r의 모든 키는 영국보다 엄격하게 큽니다. 트리는 이진 검색 트리라고 하는 이 불변량에 따라 구성됩니다.
이 불변의 주요 이점 중 하나는 정렬된 키 목록이 순서 순회를 사용하여 선형 시간으로 찾을 수 있다는 것입니다. 이것은 다음과 같이 재귀적으로 정의할 수 있습니다. - 하나의 빈 트리, 아무 작업도 수행하지 않음, 그렇지 않으면 왼쪽 하위 트리에서 먼저 재귀하여 루트를 가져오고 보고합니다. 그런 다음 오른쪽 하위 트리로 돌아갑니다.
이진 검색 트리에 대해 여러 작업을 수행할 수 있습니다. 검색은 나무의 높이를 기준으로 수행됩니다. 검색은 다른 모든 작업보다 더 중요한 작업입니다.