Trie

Read this in other languages: 简体中文, Русский, Português, Українська, 한국어

컴퓨터 과학에서 트라이는 디지털 트리라고도 불리며 때로는 기수 트리 또는 접두사 트리(접두사로 검색할 수 있기 때문에)라고도 불리며 일종의 검색 트리입니다. 키가 보통 문자열인 동적 집합 또는 연관 배열을 저장하는 데 사용되는 순서가 지정된 트리 데이터 구조입니다. 이진 검색 트리와 달리 트리의 어떤 노드도 해당 노드와 연결된 키를 저장하지 않으며 대신 트리의 위치가 해당 노드와 연결된 키를 정의합니다. 노드의 모든 하위 항목은 해당 노드와 연결된 문자열의 공통 접두사를 가지며 루트는 빈 문자열과 연결됩니다. 값은 모든 노드와 반드시 연결되지는 않습니다. 오히려 값은 나뭇잎과 관심 있는 키에 해당하는 일부 내부 노드에만 연결되는 경향이 있습니다. 접두사 트리의 공간에 최적화된 표현은 콤팩트 접두사 트리를 참조하십시오.

Made with okso.app