Двоичные деревья поиска
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
ассив, в который элементы вставляются так, что бы он сохранял свойство упорядоченности. Массив с постсортировкой это массив, в который сначала вставляются все элементы, а потом он сортируется алгоритмом быстрой сортировки. Данные таблицы, безусловно, не являются истиной в последней инстанции, но позволят вам прикинуть, какая из структур данных будет наиболее производительна в вашей программе, учитывая предполагаемую вероятность операций вставки, удаления и поиска. Так, например, массив с постсортировкой является весьма привлекательным по производительности, но совершенно не подходит для комплексных работ, так как предполагает фиксированный порядок действий сначала только добавление элементов, а после использование полученной информации. Другие структуры данных лишены этого недостатка. Для большого числа (порядка 10 000) случайных элементов время поиска в ДДП и КЧД становится практически одинаковым. Как следствие, можно реализовать более простые алгоритмы, исходя из некоторых свойств входных данных. С другой стороны, в крайнем случае (возрастающие элементы) ДДП отстают от КЧД на несколько порядков. Постоянно сортированный массив является абсолютным победителем по скорости, но не имеет естественной поддержки отношений родитель-ребёнок. Если они вам нужны, придётся реализовывать их поддержку самостоятельно. Также надо всегда помнить, что при количестве элементов порядка тысячи, асимптотические показатели скорости ещё не вполне вступили в силу и теоретически более быстрые структуры данных на практике могут оказаться более медленными. Так, например, скорость поиска в КЧД и массиве с пресортировкой до 5000-7000 практически одинакова. Так же надо заметить, что тестирование производилось на объектах относительно малого размера (8 байт), сравнимого с размером указателя (4 байта). Все виды массивов сортированных подразумевают весьма интенсивное копирование элементов, в то время как деревья работают с указателями. При размере элемента, на порядки превышающем размеры указателя, акценты сместятся весьма значительно. Например, ниже приведены результаты испытания с ключом типа int (32-x битное целое) и битовыми данными размером в 256 байт.
Количество элементовДДПКЧДПостоянно сортированный массивНе сортированный массивМассив с постсортировкой10005868
(1000)1663
(17)1430115410352000140888
(2000)3694
(19)3476246028083000368748
(3000)5815
(20)5372384843824000721328
(4000)7271
(21)72745175603550001208373
(5000)9349
(22)92476670761960001752135
(6000)11395
(22)110467778916870002501167
(7000)13503
(23)1332793781076480003334948
(8000)15753
(23)18222125601526790004266560
(9000)21600
(24)205641539117430100005421499
(10000)24105
(24)240641715219341Таблица 7. Добавление элемента (возрастающие ключи)
Количество элементовДДПКЧДПостоянно сортированный массивНе сортированный массивМассив с постсортировкой10004289132242162123020001340743036056903530300035998545796124268806400070612978713362761011215000118340595917364466015166000173069911162138690681841700024627591344249410315822518000329351915652871159274261790004215750184032842786972923100005361524206036985132683303Таблица 8. Поиск элемента (возрастающие ключи)
Количество элементовДДПКЧДПостоянно сортированный массивНе сортированный массивМассив с постсортировкой10005025831156401318371867032000118111521604342157448415928963000160215804616940465335546046264000207525378966113899948489782795000268930071484879514851393148222066000357438362157273621473162216765977000412944323038406129938188304097098000489854243901318239342862393416169000508663685019729649946077503200921000062796372630209126204958462564125Таблица 9. Удаление элемента по ключу (возрастающие ключи)
Количество элементовДДПКЧДПостоянно сортированный массивНе сортированный массивМассив с постсортировкой10001903
(24)2072
(12)579911418544820004532
(25)4739
(14)47946331071390730007747
(26)7819
(15)1727433499222440400010348
(29)10664
(15)3616654673333905500013064
(29)13652
(16)6141684831443768600016530
(31)16713
(16)92146381019153619700019305
(31)19642
(16)129818871190461301800023140
(32)23329
(16)173887651378575968900026051
(32)26378
(16)2193527915335920071000029450
(32)29448
(16)270534951707590155Таблица 10. Добавление элемента (случайные ключи)
Количество элементовДДПКЧДПостоянно сортированный массивНе сортированный массивМассив с постсортировкой100018515026616132742000695359719697472430001044586119315561124540002186823169427675170350002701110622344490523146000389814962874715492871700048831889346410955433718000418621834060165605407790006760277146962818604622100007291320153725148935384Таблица 11. Поиск элемента (случайные ключи)
Количество элементовДДПКЧДПостоянно сортированный массивНе сортированный массивМассив с постсортировкой10001235111554929111088627942000304229785578751596298558580300046414703183740147306231841029400075316494383051090081293833983500094978788667561614599142662696460001201810922102704602183259210315160700014605143761480848429779691146180918000158761607019927348399326361994611890002004319079253475714992815325384886100002211721860320490866176688432072537Таблица 12. Удаление элемента по ключу (случайные ключи)
Хорошо видно, что при увеличенном размере элемента деревья догоняют, а то и значительно обгоняют массивы. Таким образом, очевидно, что выбор структуры данных сильно зависит от предполагаемого количества элементов и их размера. Напоследок хотелось бы сказать, что правильный выбор структуры данных является одним из основных моментов, определяющих производительность программы. Поэтому подходить к выбору надо осторожно, продумав все возможные - как наиболее вероятные, так и наихудшие случаи.
Список литературы
Для подготовки данной работы были использованы материалы с сайта