Двоичные деревья поиска

37861 962 6000 1532 1142 1216 55124 1185 7000 1893 1494 1453 75628 1403 8000 2477 1833 1679 98802 1631 9000 2943 2390 1994 125570 1858 10000 3395 2937 2228 154791 2108

Таблица 5. Поиск элемента (случайные ключи)

Количество элементов ДДП КЧД Постоянно сортированный массив Несортированный массив Массив с постсортировкой
1000 469 517 1149 2014 1195
2000 995 1079 4381 8054 4387
3000 1557 1756 9673 18191 9639
4000 2272 2424 17071 32451 17105
5000 3070 3019 27380 50665 26954
6000 3528 3618 39294 72996 39227
7000 4322 4542 53255 99402 53309
8000 5299 5531 71406 129964 70766
9000 6180 6553 89583 164943 89935
10000 7527 7797 112190 202993 111439

Таблица 6. Удаление элемента по ключу (случайные ключи)

Постоянно сортированный массив – это массив, в который элементы вставляются так, что бы он сохранял свойство упорядоченности. Массив с постсортировкой – это массив, в который сначала вставляются все элементы, а потом он сортируется алгоритмом быстрой сортировки. Данные таблицы, безусловно, не являются истиной в последней инстанции, но позволят вам прикинуть, какая из структур данных будет наиболее производительна в вашей программе, учитывая предполагаемую вероятность операций вставки, удаления и поиска. Так, например, массив с постсортировкой является весьма привлекательным по производительности, но совершенно не подходит для комплексных работ, так как предполагает фиксированный порядок действий – сначала только добавление элементов, а после использование полученной информации. Другие структуры данных лишены этого недостатка. Для большого числа (порядка 10 000) случайных элементов время поиска в ДДП и КЧД становится практически одинаковым. Как следствие, можно реализовать более простые алгоритмы, исходя из некоторых свойств входных данных. С другой стороны, в крайнем случае (возрастающие элементы) ДДП отстают от КЧД на несколько порядков. Постоянно сортированный массив является абсолютным победителем по скорости, но не имеет естественной поддержки отношений родитель-ребёнок. Если они вам нужны, придётся реализовывать их поддержку самостоятельно. Также надо всегда помнить, что при количестве элементов порядка тысячи, асимптотические показатели скорости ещё не вполне вступили в силу и теоретически более быстрые структуры данных на практике могут оказаться более медленными. Так, например, скорость поиска в КЧД и массиве с пресортировкой до 5000-7000 практически одинакова. Так же надо заметить, что тестирование производилось на объектах относительно малого размера (8 байт), сравнимого с размером указателя (4 байта). Все виды массивов сортированных подразумевают весьма интенсивное копирование элементов, в то время как деревья работают с указателями. При размере элемента, на порядки превышающем размеры указателя, акценты сместятся весьма значительно. Например, ниже приведены результаты испытания с ключом типа int (32-x битное целое) и битовыми данными размером в 256 байт.

Количество элементов ДДП КЧД Постоянно сортированный массив Не сортированный массив Массив с постсортировкой
1000

5868

(1000)

1663

(17)

1430 1154 1035
2000

140888

(2000)

3694

(19)

3476 2460 2808
3000

368748

(3000)

5815

(20)

5372 3848 4382
4000

721328

(4000)

7271

(21)

7274 5175 6035
5000

1208373

(5000)

9349

(22)

9247 6670 7619
6000

1752135

(6000)

11395

(22)

11046 7778 9168
7000

2501167

(7000)

13503

(23)

13327 9378 10764
8000

3334948

(8000)

15753

(23)

18222 12560 15267
9000

4266560

(9000)

21600

(24)

20564 15391 17430
10000

5421499

(10000)

24105

(24)

24064 17152 19341

Таблица 7. Добавление элемента (возрастающие ключи)

Количество элементов ДДП КЧД Постоянно сортированный массив Не сортированный массив Массив с постсортировкой
1000 4289 132 242 1621 230
2000 134074 303 605 6903 530
3000 359985 457 961 24268 806
4000 706129 787 1336 27610 1121
5000 1183405 959 1736 44660 1516
6000 1730699 1116 2138 69068 1841
7000 2462759 1344 2494 103158 2251
8000 3293519 1565 2871 159274 2617
9000 4215750 1840 3284 278697 2923
10000 5361524 2060 3698 513268 3303

Таблица 8. Поиск элемента (возрастающие ключи)

Количество элементов ДДП КЧД Постоянно сортированный массив Не сортированный массив Массив с постсортировкой
1000 502 583 115640 131837 186703
2000 1181 1152 1604342 1574484 1592896
3000 1602 1580 4616940 4653355 4604626
4000 2075 2537 8966113 8999484 8978279
5000 2689 3007 14848795 14851393 14822206
6000 3574 3836 21572736 21473162 21676597
7000 4129 4432 30384061 29938188 30409709
8000 4898 5424 39013182 39342862 39341616
9000 5086 6368 50197296 49946077 50320092
10000 6279 6372 63020912 62049584 62564125

Таблица 9. Удаление элемента по ключу (возрастающие ключи)

Количество элементов ДДП КЧД Постоянно сортированный массив Не сортированный массив Массив с постсортировкой
1000

1903

(24)

2072

(12)

57991 1418 5448
2000

4532

(25)

4739

(14)

479463 3107 13907
3000

7747

(26)

7819

(15)

1727433 4992 22440
4000

10348

(29)

10664

(15)

3616654 6733 33905
5000

13064

(29)

13652

(16)

6141684 8314 43768
6000

16530

(31)

16713

(16)

9214638 10191 53619
7000

19305

(31)

19642

(16)

12981887 11904 61301
8000

23140

(32)

23329

(16)

17388765 13785 75968
9000

26051

(32)

26378

(16)

21935279 15335 92007
10000

29450

(32)

29448

(16)

27053495 17075 90155

Таблица 10. Добавление элемента (случайные ключи)

Количество элементов ДДП КЧД Постоянно сортированный массив Не сортированный массив Массив с постсортировкой
1000 185 150 266 1613 274
2000 695 359 719 6974 724
3000 1044 586 1193 15561 1245
4000 2186 823 1694 27675 1703
5000 2701 1106 2234 44905 2314
6000 3898 1496 2874 71549 2871
7000 4883 1889 3464 109554 3371
8000 4186 2183 4060 165605 4077
9000 6760 2771 4696 281860 4622
10000 7291 3201 5372 514893 5384

Таблица 11. Поиск элемента (случайные ключи)

Количество элементов ДДП КЧД Постоянно сортированный массив Не сортированный массив Массив с постсортировкой
1000 1235 1115 54929 111088 62794
2000 3042 2978 557875 1596298 558580
3000 4641 4703 1837401 4730623 1841029
4000 7531 6494 3830510 9008129 3833983
5000 9497 8788 6675616 14599142 6626964
6000 12018 10922 10270460 21832592 10315160
7000 14605 14376 14808484 29779691 14618091
8000 15876 16070 19927348 39932636 19946118
9000 20043 19079 25347571 49928153 25384886
10000 22117 21860 32049086 61766884 32072537

Таблица 12. Удаление элемента по ключу (случайные ключи)

Хорошо видно, что при увеличенном размере элемента деревья догоняют, а то и значительно обгоняют массивы. Таким образом, очевидно, что выбор структуры данных сильно зависит от предполагаемого количества элементов и их размера. Напоследок хотелось бы сказать, что правильный выбор структуры данных является одним из основных моментов, определяющих производительность программы. Поэтому подходить к выбору надо осторожно, продумав все возможные - как наиболее вероятные, так и наихудшие случаи.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: