Insert_data에서 prev_tmp를 지웠을 때, 성능향을 기대할 수 있을까요?

6 asked

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 함수가 여러 번 호출 되었을 때 성능상 이점이 되리라 생각 됩니다.