저는 AVL 트리가 정수와 어떻게 작동하는지 이해합니다. 그러나 문자열을 하나에 삽입하는 방법을 찾는 데 어려움을 겪고 있습니다. 문자열은 어떻게 비교 될까요?C++에서 AVL 트리에 문자열 삽입?
나는 ASCII 총계 값을 사용하여 그런 식으로 정렬하는 것을 생각해 보았습니다.하지만 그런 상황에서 두 개의 동일한 ASCII 단어 (예 : "묶음"과 "다이어트")을 삽입하면 오류가 반환되는 것처럼 보입니다.
어떻게이 문제를 해결할 수 있습니까? 내가 잘못 생각하고 노드를 정렬하는 다른 방법이 필요합니까?
아니요. 알파벳순이 아니어도 상관 없습니다. AVL 트리에서만 볼 수 있으므로 빠르게 검색 할 수 있습니다.
문자열을 사용하는 경우 일반적으로 어휘 비교를 사용합니다. 즉, 각 문자열의 첫 문자로 시작합니다. 하나가 다른 것보다 작 으면 (예 : "다이어트"대 "묶음", "d"가 "t"미만) 비교는 해당 문자를 기반으로합니다. 첫 번째 글자가 동등한 경우에만 두 번째 글자로 이동합니다. 두 문자열은 문자열의 처음부터 끝까지 모든 문자가 (순서대로) 동일한 경우에만 동일합니다.
AVL 트리는 정렬 된 구조이므로 int string::compare(const string&) const 루틴은 문자열을 정렬하는 방법을 알려줄 수 있어야합니다.
항목의 순서가 실제로 관련이없는 경우 수행하려는 작업을 더 잘 활용할 수있는 정렬되지 않은 구조에서 더 나은 성능을 얻을 수 있습니다 (hash table).
문자열과 같은 고정 크기 키 매핑을 hash function이라고하며, 여러 키가 동일한 값으로 매핑되는 현상을 collision이라고합니다. 충돌은 해싱 할 때가끔 발생하며, 기본 데이터 구조를 처리하기 위해 확장해야 할 필요가 있습니다. 아마도 각 노드를 "버켓"(링크 된 목록, 벡터, 배열, 무엇을 가지고 있습니까?) 선형 적으로 검색되는 해시 값을 충돌시킵니다.
해시 테이블이 트리보다 반드시 빠를 필요는 없습니다. 그것은 모두 크기에 달려 있습니다 (물론 해시 함수가 좋다는 가정하에). AVL 트리는 나쁜 대안이 아닙니다. – valdo
'compare'는 오래된 C와 같은 메소드입니다. 'std :: string'은 당연히'operator <'를 지원합니다. 이것은 제 경험에서 이해하기가 훨씬 쉽습니다. –
@valdo 동의 함; 개인적으로는 AVL 트리를 좋아하지만 순서가 지정된 키만 있으면 좋겠지 만 실제로는 실제로는 빨강 - 검정 나무가 더 자주 구현됩니다. 순서가 중요하지 않은 경우 해시 테이블을 사용하면 더 많은 공간/속도 트레이드 오프 유연성을 얻을 수 있으며 높은 채우기/큰 버킷으로 인해 너무 느려지면 크기를 조정할 수 있습니다. –
'int string :: compare (const string &) const'는 어휘 비교입니다. –