Часть 2. «Двоичные деревья поиска».

2019-12-29

194

Обсуждений (0)

0.00 из 5.00 0 оценок

Часть 1. «Быстрая сортировка».

1. Изучение алгоритма:

Быстрая сортировка относится к алгоритмам «разделяй и властвуй».

Алгоритм состоит из трёх шагов:

1) Выбрать элемент из массива (последний элемент). Назовём его опорным.

2) Разбиение: перераспределение элементов в массиве таким образом, что элементы меньше опорного помещаются перед ним, а больше или равные после.

3) Рекурсивно применить первые два шага к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы.

2. Схема алгоритма :

3. Пример сортировки:

№	Массив A
0	{3,0,1,8,7,2,5,4,9,6}
1	{3,0,1,6,7,2,5,4,9,8}
2	{3,0,1,4,7,2,5,6,9,8}
3	{3,0,1,4,6,2,5,7,9,8}
4	{3,0,1,4,5,2,6,7,9,8}
5	{2,0,1,4,5,3,6,7,9,8}
6	{1,0,2,4,5,3,6,7,9,8}
7	{0,1,2,4,5,3,6,7,9,8}
8	{0,1,2,3,5,4,6,7,9,8}
9	{0,1,2,3,4,5,6,7,9,8}
10	{0,1,2,3,4,5,6,7,8,9}

4. Текст программы :

1. lea ebx, [A]

2. mov si, bx

3. mov di, bx

4. mov ax, 3 ;kolichestvo elementov

5. dec ax

6. mov dl, 2

7. mul dl ;tk dw

8. add si, ax

9. push esi

10. mov ebp, esi

11. mov dl, 1

12. mov dh, 0

13. jmp pervaya

14. vtoraya:

15. cmp esi, edi

16. je perehod

17. push esi

18. podchast1:

19. cmp esi, ebp

20. jnl konec

21. cmp esi, edi

22. jng podchast3rs

23. podchast2ls:

24. lea ebx, [A]

25. dec esi

26. dec esi

27. jmp pervaya

28. perehod:

29. add edi, esi

30. podchast3rs:

31. pop esi

32. mov ebx, esi

33. inc ebx

34. inc ebx

35. pop esi

36. push esi

37. cmp esi, ebp

38. je perehod2

39. dec esi

40. dec esi

41. perehod2:

42. cmp ebx, esi

43. je podchast1

44. pervaya:

45. mov ecx, esi

46. sub ecx, ebx

47. cmp ecx, 0

48. jle vtoraya

49. cmp dl, dh

50. jg sravnenie1

51. jmp sravnenie2

52. sravnenie1:

53. mov ax, [ebx]

54. mov cx, [esi]

55. cmp ax, cx

56. jg zamena

57. inc bx

58. inc bx

59. jmp pervaya

60. sravnenie2:

61. mov ax, [ebx]

62. mov cx, [esi]

63. cmp ax, cx

64. jg zamena

65. dec si

66. dec si

67. jmp pervaya

68. zamena:

69. mov [ebx], cx

70. mov [esi], ax

71. xchg dl, dh

72. jmp pervaya

73. konec:

74. mov dl, 1

75. ret

76. section .data

77. A dw 0x3, 0x7, 0x4

5. Трассировочная таблица:

№	EAX	EBX	ECX	ESI	EDI	EBP	DL	DH	STACK	MAS
1	?	0x402000	?	?	?	?	?	?	?	{3,7,4}
2	?	-	?	0x402000	?	?	?	?	?	-
3	?	-	?	-	0x402000	?	?	?	?	-
4	3	-	?	-	-	?	?	?	?	-
5	2	-	?	-	-	?	?	?	?	-
6	-	-	?	-	-	?	2	?	?	-
7	4	-	?	-	-	?	-	?	?	-
8	-	-	?	0x402004	-	?	-	?	?	-
9	-	-	?	-	-	?	-	?	0x402004	-
10	-	-	?	-	-	0x402004	-	?	-	-
11	-	-	?	-	-	-	1	?	-	-
12	-	-	?	-	-	-	-	0	-	-
13	-	-	?	-	-	-	-	-	-	-
45	-	-	0x402004	-	-	-	-	-	-	-
46	-	-	4	-	-	-	-	-	-	-
47-50	-	-	-	-	-	-	-	-	-	-
53	3	-	-	-	-	-	-	-	-	-
54	-	-	4	-	-	-	-	-	-	-
55-56	-	-	-	-	-	-	-	-	-	-
57-58	-	0x402002	-	-	-	-	-	-	-	-
59	-	-	-	-	-	-	-	-	-	-
45	-	-	0x402004	-	-	-	-	-	-	-
46	-	-	2	-	-	-	-	-	-	-
47-50	-	-	-	-	-	-	-	-	-	-
53	7	-	-	-	-	-	-	-	-	-
54	-	-	4	-	-	-	-	-	-	-
55-56	-	-	-	-	-	-	-	-	-	-
69	-	-	-	-	-	-	-	-	-	{3,4,4}
70	-	-	-	-	-	-	-	-	-	{3,4,7}
71	-	-	-	-	-	-	0	1	-	-
72	-	-	-	-	-	-	-	-	-	-
45	-	-	0x402004	-	-	-	-	-	-	-
46	-	-	2	-	-	-	-	-	-	-
47-51	-	-	-	-	-	-	-	-	-	-
61	4	-	-	-	-	-	-	-	-	-
62	7	-	-	-	-	-	-	-	-	-
63-64	-	-	-	-	-	-	-	-	-	-
65-66	-	-	-	0x402002	-	-	-	-	-	-
67	-	-	-	-	-	-	-	-	-	-
45	-	-	0x402002	-	-	-	-	-	-	-
46	-	-	0	-	-	-	-	-	-	-
47-48	-	-	-	-	-	-	-	-	-	-
15-16	-	-	-	-	-	-	-	-	-	-
17	-	-	-	-	-	-	-	-	0x402002	-
19-22	-	-	-	-	-	-	-	-	-	-
23	-	0x402000	-	-	-	-	-	-	-	-
24-25	-	-	-	0x402000	-	-	-	-	-	-
26	-	-	-	-	-	-	-	-	-	-
45	-	-	0x402000	-	-	-	-	-	-	-
46	-	-	0	-	-	-	-	-	-	-
47-48	-	-	-	-	-	-	-	-	-	-
15-16	-	-	-	-	-	-	-	-	-	-
29	-	-	-	-	0x804000	-	-	-	-	-
31	-	-	-	0x402002	-	-	-	-	0x402004	-
32	-	0x402002	-	-	-	-	-	-	-	-
33-34	-	0x402004	-	-	-	-	-	-	-	-
35	-	-	-	0x402004	-	-	-	-	?	-
36	-	-	-	-	-	-	-	-	0x402004	-
37-38	-	-	-	-	-	-	-	-	-	-
42-43	-	-	-	-	-	-	-	-	-	-
19-20	-	-	-	-	-	-	-	-	-	-
74	-	-	-	-	-	-	1	-	-	-
75	-	-	-	-	-	-	-	-	-	-

6. Анализ сложности алгоритма:

Ясно, что операция разделения массива на две части относительно опорного элемента занимает время: O(log₂n). Поскольку все операции разделения, проделываемые на одной глубине рекурсии, обрабатывают разные части исходного массива, размер которого постоянен, суммарно на каждом уровне рекурсии потребуется также O(n) операций. Следовательно, общая сложность алгоритма определяется лишь количеством разделений, то есть глубиной рекурсии. Глубина рекурсии, в свою очередь, зависит от сочетания входных данных и способа определения опорного элемента.

Лучший случай: O(n*log₂n)

Среднее: O(n*logn)

Худший случай: O(n²)

7. Отчёт:

Один из самых быстродействующих (на практике) из алгоритмов внутренней сортировки общего назначения. Прост в реализации. Однако сильно деградирует по скорости в худшем или близком к нему случае, что может случиться при неудачных входных данных. Прямая реализация в виде функции с двумя рекурсивными вызовами может привести к ошибке переполнения стека, так как в худшем случае ей может потребоваться сделать O(n) вложенных рекурсивных вызовов. Неустойчив.

Часть 2. «Двоичные деревья поиска».

1. Структура данных:

Двоичное дерево поиска записывается в один массив. Для хранения информации об одном узле необходимо четыре байта. Место под данные резервируется с помощью директивы db. В первом байте – значение узла; во втором – относительный номер строки меньшего по значению потомка; в третьем – относительный номер строки большего по значению потомка; в четвертом – «0», так как необходимо расширение до степени 2.

Порядок работы программы:

1) Поиск вводимого элемента итеративным способом.

2) Добавление вводимого элемента в дерево (пропуск, если элемент был найден).

3) Поиск следующего вводимого элемента рекурсивным способом.

4) Добавление вводимого элемента в дерево (пропуск, если элемент был найден).

5) Обход дерева и вывод всех элементов в порядке возрастания.

2. Схемы алгоритмов:

1) Рекурсивный поиск:

2) Итеративный поиск:

3) Добавление элементов:

4) Обход дерева:

3. Код программы :

1) xor eax, eax

2) mov ebp, len

3) shr ebp, 2

4) call Iterativnii_poisk

5) call Rekursivnii_poisk

6) Obhod_dereva:

lea ebx, [A]

7) xor ah, ah

8) mov ebp, 1

9) push ebp

10) print_tree:

mov al, [ebx+1]

11) cmp al, 0

12) je skip_l

13) push ebx

14) shl ax, 2

15) add bx, ax

16) call print_tree

17) skip_l:

mov al, [ebx]

18) PRINT_DEC 1, al

19) PRINT_STRING [Pr]

20) mov al, [ebx+2]

21) cmp al, 0

22) je skip_r

23) push ebx

24) shl ax, 2

25) add bx, ax

26) call print_tree

27) skip_r:

pop ebx

28) pop ebx

29) cmp ebx, ebp

30) je konec

31) mov cl, [ebx+1]

32) cmp cl, 0

33) je obnulit

34) mov cl, 0

35) mov [ebx+1], cl

36) call print_tree

37) obnulit:

mov [ebx+2], cl

38) jmp skip_r

39) konec:

NEWLINE

40) PRINT_STRING [Print5]

41) ret

42) Iterativnii_poisk:

pop eax

43) push eax

44) GET_DEC 1, dl

45) lea ebx, [A]

46) lea esi, [A]

47) xor edi, edi

48) xor ecx, ecx

49) poisk2:

mov cl, [ebx]

50) cmp cl, dl

51) je goodend2

52) cmp di, 2

53) je noviiuzel

54) cmp di, 1

55) je praviisin

56) leviisin:

inc di

57) mov ebx, esi

58) mov cl, [esi+1]

59) cmp cl, 0

60) je praviisin

61) shl cl, 2

62) add bl, cl

63) push ebx

64) jmp poisk2

65) praviisin:

inc di

66) mov ebx, esi

67) mov cl, [esi+2]

68) cmp cl, 0

69) je noviiuzel

70) shl cl, 2

71) add bl, cl

72) push ebx

73) jmp poisk2

74) noviiuzel:

inc ch

75) add ecx, ebp

76) cmp ch, cl

77) je badend2

78) pop esi

79) xor di, di

80) jmp leviisin

81) badend2:

PRINT_STRING [Print1]

82) PRINT_DEC 1, dl

83) PRINT_STRING [Print3]

84) PRINT_STRING [Print2]

85) NEWLINE

86) call Dobavlenie_elementa

87) ret

88) goodend2:

cmp eax, ecx

89) je vivod

90) pop ecx

91) jmp goodend2

92) vivod:

push ecx

93) PRINT_STRING [Print1]

94) PRINT_DEC 1, dl

95) PRINT_STRING [Print2]

96) NEWLINE

97) ret

98) Rekursivnii_poisk:

GET_DEC 1, dl

99) lea ebx, [A]

100) xor ecx, ecx

101) sub esp, 4

102) poisk:

add esp, 4

103) mov al, [ebx]

104) cmp al, dl

105) je goodend

106) jl menshe

107) mov cl, [ebx+1]

108) cmp cl, 0

109) je badend

110) shl cl, 2

111) add bx, cx

112) call poisk

113) menshe:

mov cl, [ebx+2]

114) cmp cl, 0

115) je badend

116) shl cl, 2

117) add bx, cx

118) call poisk

119) badend:

PRINT_STRING [Print1]

120) PRINT_DEC 1, dl

121) PRINT_STRING [Print3]

122) PRINT_STRING [Print2]

123) NEWLINE

124) call Dobavlenie_elementa

125) ret

126) goodend:

PRINT_STRING [Print1]

127) PRINT_DEC 1, dl

128) PRINT_STRING [Print2]

129) NEWLINE

130) ret

131) Dobavlenie_elementa:

lea ebx, [A]

132) lea esi, [A]

133) push ebp

134) shl ebp, 2

135) add esi, ebp

136) pop ebp

137) xor ecx, ecx

138) sub esp, 4

139) sravnenie:

add esp, 4

140) mov al, [ebx]

141) cmp al, dl

142) jl elem_bolshe

143) mov cl, [ebx+1]

144) cmp cl, 0

145) je pomeshchenie

146) shl cl, 2

147) add bx, cx

148) call sravnenie

149) elem_bolshe:

mov cl, [ebx+2]

150) cmp cl, 0

151) je pomeshchenie

152) shl cl, 2

153) add bx, cx

154) call sravnenie

155) pomeshchenie:

mov eax, esi

156) mov ecx, ebx

157) cmp dl, [ebx]

158) jg bolshe_uzla

159) sub eax, ecx

160) shr eax, 2

161) mov [ebx+1],al

162) jmp uvelichenie_massiva

163) bolshe_uzla:

sub eax, ecx

164) shr eax, 2

165) mov [ebx+2],al

166) uvelichenie_massiva:

mov [esi], dl

167) mov ecx, 3

168) xor eax, eax

169) c1:

inc esi

170) mov [esi], al

171) loop c1

172) inc ebp

173) PRINT_STRING [Print1]

174) PRINT_DEC 1, dl

175) PRINT_STRING [Print4]

176) NEWLINE

177) ret

178) section .data

179) A db 15, 1, 2, 0

db 10, 0, 0, 0

db 20, 0, 0, 0

180) len equ $-A

181) Pr db " ", 0

182) Print1 db " Элемент ", 0

183) Print2 db " найден", 0

184) Print3 db " не", 0

185) Print4 db " добавлен", 0

186) Print5 db " Задача выполнена", 0

4. Трассировочная таблица:

Дерево: Ввод и вывод:

№

eax

ebx

ecx

edx

ebp

esi

edi

stack

вывод

0x0

0xc

0x3

0xa

0x4030d0

0x0

0xf

50-55

0x1

59-60

0x4

0x4030d4

<>,0x4030d4

0xa

50-51

88-89

0x4030d4

88-89

93-96

Элемент 10 найден

0x19

0x4030d0

100

0x0

101-102

103

0x40130f

104-106

113

0x2

114-115

116

0x8

117

0x4030d8

118

119

<>,<>

102

103

0x401314

104-106

113

0x0

114-115

119-123

Элемент 10 найден
Элемент 25 не найден

124

<>,<>

131

0x4030d0

132

0x4030d0

133

<>,<>,0x3

134

0xc

135

0x4030dc

136

0x3

<>,<>

137

0x0

138-139

140

0x40130f

141-142

149

0x2

150-151

152

0x8

153

0x4030d8

154

<>,<>,<>

139

<>,<>

140

0x401314

141-142

149

0x0

150-151

155

0x4030dc

156

0x4030d8

157-158

163

0x4

164

0x1

165

Добавление относительного номера строки в массив для узла-родителя

166

Добавление элемента в массив

167

0x3

168

169

0x4030dd

170

171

0x2

169

0x4030de

170

171

0x1

169

0x4030df

170

171

0x0

172

0x4

173-176

Элемент 10 найден
Элемент 25 не найден

Элемент 25 добавлен

177

125

0x4030d0

0x0

0x1

11-12

0x1, 0x4030d0

0x4

0x4030d4

0x1, 0x4030d0,<>

0x0

11-12

0xa

18-19

Элемент 10 найден
Элемент 25 не найден

Элемент 25 добавлен
10

0x0

21-22

0x1, 0x4030d0

0x4030d0

0x1

29-30

0x1

32-33

0x0

Обнуление относительного номера строки

0x1,<>

0x0

11-12

0xf

18-19

Элемент 10 найден
Элемент 25 не найден

Элемент 25 добавлен
10 15

0x2

21-22

0x1,<>, 0x4030d0

0x8

0x4030d8

0x1,<>, 0x4030d0,<>

0x0

2019-12-29

194

Обсуждений (0)

0.00 из 5.00 0 оценок

Обсуждение в статье: Часть 2. «Двоичные деревья поиска».

Обсуждений еще не было, будьте первым... ↓↓↓