inflearn logo
강의

Khóa học

Chia sẻ kiến thức

Các cấu trúc dữ liệu và thuật toán nguồn mở trong C

Hàm insert của Cây tìm kiếm nhị phân 2

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

260

Kumma

6 câu hỏi đã được viết

0

제 생각으로는 성능 향상이 거의 없다고 생각이 되는데, 궁금합니다!

1 . 트리의 특성 상, Insert 내의 While() 1번은 사실 상 2^n개의 데이터를 순회하는 효과니까 데이터가 정말 많아도 100번 이하로 돌 것 같습니다.

2. 대입문 1개는 지우는건 어셈블리 1줄을 지우는 거니까, 100줄 정도의 어셈이 사라지는 것인데, 이게 큰 성능향상인지 궁금합니다!

c linux 알고리즘 gcc data-structure

Câu trả lời 1

1

jikim1770

안녕하세요.

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

동영상 재생이 안됩니다.

1

32

1

mingw-w64설치가 안됩니다.

0

46

2

signal함수와 관련하여 질문있습니다.

0

33

1

수정 자료 요청

0

62

1

강의 슬라이드 문서 자료에 24~28강 자료가 누락된것 같습니다.

0

51

1

강의 슬라이드 문서 자료에 24~28강 자료가 누락된것 같습니다.

0

73

2

쓰레드 상태 관련 질문입니다.

0

62

2

다운로드 받은 교안에 해당 내용이 없는것 같습니다.

0

59

3

runpod에서 실습하는 내용이 조금 다릅니다.

0

49

1

DACL 질문

0

64

1

DLL 제작자가 PDB도 같이 제공해야 한다는 설명에 질문

0

53

2

정처기 2026-3 실기 문의

0

121

2

정처기 실기 3회 컴싸 사용 여부

0

85

1

모의고사 1 회 2번문제 중

0

90

2

26-2 이론문제 재탕

1

66

1

26-2년도 코드문제

0

42

0

26-2 코드문제

0

54

1

15분 48초 질문

0

76

2

26-1년도 이론문제 재탕

0

77

1

26-1년도 코드문제 재탕

0

55

0

vi 명령어

0

100

1

tail노드의 이유 & 메모리 풀링 관련

0

405

2

커널 버전

0

310

1

메모리 풀링 속도 확인

0

388

1