|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Shatalov 2:5020/400 19 Sep 2002 17:35:01
To : All
Subject : Re: [Q] Быстpый поиск в отсоpтиpованном списке
--------------------------------------------------------------------------------
Привет, Андрей!
> Создали и добавили 1, 2, 3 Удалили 2. Создали и добавили 4... и т.д.
> Отсортировали результат - требуется назвать _индекс_ бывшего третьего...
Ватсон, это же элементарно! (с)
1) Создали список.
2) Занесли 1,2,3 на позиции 1,2,3.
3) Удалили 2 с позиции 2. Получили список из двух элементов 1,3. При этом
элемент 3 сдвигается на одну позицию и занимает место элемента 2.
4) Добавили 4 на позицию 3. Получили список 1,3,4.
5) Добавили 10 на позицию 4. Получили список 1,3,4,10.
6) Добавили 2 на позицию 2. При этом элементы 3,4,10 сдвигаются на одно
позицию и получается список 1,2,3,4,10.
Hичего сортировать не надо, список и так отсортирован.
Поиск позиции, куда вставить новый элемент, производится все тем же
двоичным поиском.
При этом памяти нужно в три раза меньше чем для хранения двоичного дерева
(4 байта на индекс вместо 12 байт (индекс ветви и два указателя на левую и
правую дочерние ветви)).
Единственный минус, как я уже говорил выше, это сдвиг массива при вставке
внутрь или при удалении элемента внутри массива.
Пока,
Олег.
--- ifmail v.2.15dev5
* Origin: Golden Triangle On Line Inc. (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
