인프런 커뮤니티 질문&답변
작성한 질문수
Insert_data에서 prev_tmp를 지웠을 때, 성능향을 기대할 수 있을까요?
작성
·
201
0
제 생각으로는 성능 향상이 거의 없다고 생각이 되는데, 궁금합니다!
1 . 트리의 특성 상, Insert 내의 While() 1번은 사실 상 2^n개의 데이터를 순회하는 효과니까 데이터가 정말 많아도 100번 이하로 돌 것 같습니다.
2. 대입문 1개는 지우는건 어셈블리 1줄을 지우는 거니까, 100줄 정도의 어셈이 사라지는 것인데, 이게 큰 성능향상인지 궁금합니다!
퀴즈
59%나 틀려요. 한번 도전해보세요!
그래프와 구별되는 트리의 핵심 특징 중 하나는 무엇일까요?
모든 노드가 연결되어 있다.
임의의 두 노드 사이에 유일한 경로가 존재한다.
최상위 노드인 루트(Root)가 있다.
노드와 간선으로 구성된다.
답변 1
1
김정인
지식공유자
안녕하세요.
tree 의 insert_data 함수의 개선 과정을 문의 하신 것 같습니다.
해당 소스를 보면
if( root == 0 )
{
root = temp;
return;
}
while(p)
{
prev = p;
if( p->data > data )
p=p->left;
else if( p->data < data )
p=p->right;
else
return;
}
if( prev->data > data )
prev->left = temp;
else
prev->right = temp;위 부분이 아래와 같이 바뀐 것이므로
while(*p)
{
if( (*p)->data > data )
p=&(*p)->left;
else if( (*p)->data < data )
p=&(*p)->right;
else
return;
}
*p = temp;while 루프 안의
prev = p 가 사라진 것과
while 아래 쪽의 if ~ else 구문이 사라진 것이 주요 합니다.
while 루프 안의 코드 삭제는 log N 번 이라 하더라도 데이터가 많은 경우 성능 향상을 기대할 수 있습니다.
또한 While 아래쪽의 if ~ else 또한 while 안쪽은 아니지만 insert_data 함수가 여러 번 호출 되었을 때 성능상 이점이 되리라 생각 됩니다.