질문 게시판 / Q&A

bts +순서 질문이 있습니다

by whoRu, 11월 17일, 16:52

문제를 봤는데 명령어 형식 + 에 bts에 들어갈 위치를 찾는다곤 되어있는데 기준이 명확하게 나와있지 않은 것 같아 질문드립니다
예시를 봤을때는 단어의 첫글자를 기준으로 알파벳순으로 내려가는것 같은데 맞을까요...?
그리고 만약에 알파벳순이 맞을경우에 한쪽으로 트리가 치우쳐도 문제가 없는 건지 여쭤보고 싶습니다!

whoRu , 11월 17일, 18:29
 감사합니다! 정확하게 이해했습니다 
prof , 11월 17일, 18:18
 roght-skewed -> right-skewed 
prof , 11월 17일, 18:17
 단어 "크기"는 문자열 그 자체로 비교된 결과를 따릅니다.
사전식(lexicographical) 순서입니다. 궁금하면 

vector<string> my ; 에 모두 넣고 sort( )을 해보면 됩니다. 

트리는 입력순서에 따라서 결정됩니다. 따라서
a, b, c... 이렇게 들어오면 roght-skewed tree가 됩니다.
그래서 BST를 개선해서 height balanced tree를 만들지요. 
assist , 11월 17일, 18:16
 추가 순서는 사전식입니다. 들어갈 문자열이 해당 노드보다 사전식으로 빠르면 왼쪽, 아니면 오른쪽에 추가합니다. (관련 설명을 추가하여 과제물 목록의 설명에 업로드하겠습니다. )

따라서 한쪽으로 트리가 치우칠 수 있습니다.