Устройство для поиска информации

 

Изобретение относится к вычислительной технике и может быть использовано в системах управления базами данных. Цель изобретения - упрощение устройства. Устройство содержит регистр 1, элемент И 3, элемент 15 задержки, генератор 19 импульсов, группы 2, 13 и 14 элементов И, группу 10 элементов ИЛИ, регистр 11, элемент 4 сравнения, регистр 5, блок 12 памяти, триггеры и элементы ИЛИ. Устройство обеспечивает поиск записи с заданным ключом с любого адреса исходного массива, представляющего собой бинарную древовидную структуру, в которой каждая запись сопровождается, кроме того, левым и правым указателями. В полях указателей узлов бинарного дерева, не имеющих непосредственных потомков, содержится ссылка на корень. Если поиск начинается с левого поддерева записи, находящейся в правом поддереве, то производится нахождение корня, а затем переход в правое поддерево. При отсутствии записи процедура поиска обеспечивает двойное прохождение корня, на основе которого формируется сигнал "Отсутствие записи". 3 ил.

СООЗ СОВЕТСНИХ, СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

09) Oll

0 96 А1 (51)5 С 06 F 15 40

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЦТИЯМ

ПРИ ГННТ СССР

t (2.,1) 4483469/24-24 (22) 16.09.88 (46) 23.07.90. Бюл. И 27 (72) В,Г.Попов и С.А.Удинцев (53) 62.1:325(088.8} (56) Авторское свидетельство СССР

Ф 12068 10, кл. С 06 F 15/40, 1984., Авторское свидетельство СССР

В 1325514, кл. С 06 F 15/40, 1986. (54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРИА151И (57) Изобретение относится к вычислительной технике и может быть использовано в системах управления базами данных. Цель изобретения — упрощение устройства. Устройство содержит регистр 1, элемент И 3, элемент

15 задержки, генератор 19 импульсов, группы 2, 13 и 14 элементов И, груп пу 10 элементов ИЛИ, регистр 11, элемент 4 сравнения,.регистр 5, блок 12 памяти, триггеры и элементы ИЛИ.

Устройство обеспечивает поиск записи с заданным ключом с любого адреса исходного массива, представляющего собой бинарную древовидную структуру, в которой каждая запись сопровождается, кроме того, левым и правым указателями.

B полях указателей узлов бинарного дерева, не имеющих непосредственных потомков, содержится ссылка на корень. Если поиск начинается с левого поддерева записи, находящейся в правом поддереве, то производится нахождение корня, а затем переход в правое поддерево. При отсутствии записи процедура поиска обеспечивает двойное прохождение корня, на основе которого формируется сигнал "Отсуттвие записи". 3 ил.

1580396

Изобретение относится к вычислительной технике и может быть использовано в системах управления базами данных.

Цель изобретения — упрощение устройства.

На фиг.1 показана структурная схема устройства; на фиг.2 — пример бинарного дерева; на фиг.3 — его разме- 1О щение в блоке памяти.

Устройство содержит регистр 1, группу 2 элементов И, элемент И 3, элемент 4 сравнения, регистр 5,включающий поле 6 данных, поле 7 ключа записи, поле 8 адреса левого указателя, поле .9 адреса правого указателя, группу 10 элементов ИЛИ, регистр

11, блок 12 памяти, группы 13 и 14 элементов И, элемент 15.задержки, 2п элемент ИЛИ 16 с инверсным выходом, элемент И 17, элемент И 18, генератор 19 импульсов, триггер 20, элемент

И 21, триггер 22, элемент ИЛИ 23, дифференцирующий элемент 24, выход 25

25 "Равно-", выход 26 "Меньше" и выход 27 "Больше" элемента 4, вход 28 адреса устройства, выход 29 гбтовности устройства, вход 30 запуска устройства, выход 31 "Отсутствие записи" устройства, вход 32 ключа устройства, информационный выход 33 устройства.

Рассмотрим принципы построения и работу устройства.

Устройство предназначено для поиска информации со структурой бинарного дерева. Для организации бинарного дерева каждая ячейка памяти содержит четыре поля: ключа, левого указателя, 40 правого указателя и данных. В поле

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

Пусть необходимо разместить в поле памяти данные с идентификаторами, значения которых лежат в пределах чисел натурального ряда от 1 до 18.

Бинарное дерево для данного случая показано на фиг.2. Оно содержит узлы, где цифрами указано значение ключа, 55 а знаками (и > отмечены поле левого и правого указателей. Узел с ключом, равным 9, является корнем дерева. Узлы с ключами от 1 до 8 образуют левое дерево, а узлы с ключами от !О до 18 - правое поддерево.

Узлы, не имеющие левого или правого . указателя, помечаются ссылкой на адрес ячейки, где размещен адрес корневого узла, Пример отображения дерева на память показан на фиг.3, где слева указаны адреса ячеек памяти с 101 по

119. Адресом корня является адрес, равный 109. Этот адрес размещается в узлах, не имеющих указателей.

Пусть необходимо сосчитать данные, ключ которых равен 16.Исходное

/ состояние устройства характеризуется тем, что триггеры 20 и 22 установлены в состояние "0" (не показано).

По входу 28 через элементы ИЛИ 10 в регистр 11 записывается начальный адрес дерева А „ = 101, а по входу

Э

32 в регистр 1 — ключ искомого узла (записи) Клд= 16.

Поиск данных инициируется подачей сигнала пуска по входу 30. По этому сигналу триггер 22 устанавливается в

"1", открывая элемент И 17. По первому импульсу генератора 19 осуществляется прием содержимого ячейки с адресом 101 в регистр 5.

Так как ключ в регистре 1 больше считанного ключа в поле 7 регистра 5 (16 > 1), то на выходе 27 "Больше" элемента 4 формируется единичный сигнал, по которому открываются элементы

И 13. При появлении импульса на выходе элемента 15 задержки адрес правого указателя из поля 9 регистра 5 через элементы И 13 и ИЛИ 10 передается в регистр 11, где устанавливается адрес

А = 102.

Время задержки элемента 15 определяется временем переходных процессов в регистре 5 и элементе 4 сравнения.

После чтения информации в регистре 5

Кл „ > КЛ (16 0 2) и рассмотренным порядком в регистр 5 принимается информация по адресу 119, Так как ключ этого узла равен нулю, то на выходе

27 "Больше" удерживается единичный сигнал, по которому в регистр 5 считывается информация по корневому узлу.

В дальнейшем поиск данных продолжается в правом поддереве в соответствии с рассмотренным с последовательным формированием адресов А, А и

А, Когда в регистре 5 находится информация с корневого узла, на выходе элемента 4 удерживается единичный сигнал, по которому определяется передача адреса корня А > в регистр 11.

После приема информации в регистр

5 из ячейки с А т 119 на выходе поля 7 устанавливаются нулевые сигналы (Клэ = О). При этом на выходе элемента ИЛИ 16 формируется единичный сигнал, открывающий элемент И 18 °

Задержанным импульсом с выхода эле" мента t5 задержки триггер 20 устанавливается в нулевое состояние. С помощью дифференцирующего элемента 24 формируется импульс, которым через элемент ИЛИ 23 триггер 22 устанавливается в нулевое состояние. Таким образом, на выходах 29 и 31 установлены единичные сигналы, что свидетельствует об отсутствии записи с заданным ключом (Кл „ = !9) в блоке 12 памяти.

Поиск записи с ключом, находящимся в левом поддереве, осуществляется аналогично рассмотренному, но без перехода через корень в правое поддерево, если поиск начинается с начального адреса А „.

Формула

Устройство для поиска информации, содержащее группу элементов ИЛИ, ":ри группы элементов И, блок памяти, три регистра, элемент сравнения„ четыре элемента И, элемент задержки, генератор импульсов и два элемента KlH выход генератора импульсов соединен с первым входом первого элемента И, выход котоПого через элемент задержки соединен с первыми входами элементов

И первой н второй групп и первыми входами второго и третьего элементов И, первые входы элементов ИЛИ группы являются адресным. входом устройстI ва, выходы элементов И первой и второй групп соединены с вторыми и третьими входами элементов ИЛИ группы соответственно, выходы элементов

ИЛИ группы соединены с информационными входами первого регистра, выход которого соединен с адресным входом блока памяти, выход которого соединен с информационным входом второго регистра, выходы разрядов данных котоментов И третьей группы, выходы которых являются информационными выходами устройства, выход первого элемента

З

5 1580396 6 элемента ИПИ 16 формируется единичный сигйал (так как КЛ О), открывающий элемент И 18. Задержанный им. пульсом генератора 19 с выхода элемента 15 задержки через элемент И 18 устанавливается по счетному входу в "1" триггер 20.

От момента приема информации в регистр 5 до момента установки триггера 20 в единичное состояние при данной ситуации на выходе 31 "Отсутствие записи" формируется единичный сигнал. Но так как триггер 22 находится в единичном состоянии, то на выходе 29 сигнал готовности устройства к чтению отсутствует. Поэтому единичный сигнал на выходе 31 не

Ф принимается во внимание.

Когда в регистре 11 окажется ин- 20 формация, сосчитанная по адресу А =

118, на выходе 26 "Меньше" элемента 4 формируется единичный сигнал, так как Кл„ < KJI > (16 < 18), Данным сигналом определяется передача ад- 25 реса А, = 116 из поля 8 регистра 5 через элементы И 14 и ИЛИ 10 в регистр 11.

После приема информации в регистр

11 из ячейки с А 1 = 116 на первом изобретения и втором входах элемента 4 устанавливаются одинаковые ключи (Кл „ = Кл ).

При этом на выходе 25 "Равно" зль— мента 4 формируется единичный сигнал, по которому данные из поля 6 регист35 ра 5 передаются на выход 33 через элементы И 2 по задержанному импульсу, проходящему через открытый в данном . случае элемент И 3. Этим же сигналом через элемент ИЛИ 23 триггер 22 40 устанавливается в нулевое состояние.

Единичный сигнал с единичного выхода триггера 22 подается на выход 29 и используется в качестве сигнала готовности устройства к чтению. Так как 45 на выходе 31 сигнал отсутствует,то производится обращение к устройству за данными, передаваемыми на выход

33 через элементы И 2.

Пусть требуется сосчитать данные, ключ которых равен 19. Для этого устройство приводится к исходному состоянию и запускается сигналом пуска по входу 30. Работа устройства при формировании в регистре 11 55 адресов А — А аналогична рассмот- рого соединены с первыми входами эле5 ренной.

Когда в регистре 11 окажется адрес А = 118, на выходе 27 "Больше"

7 158039

И соединен с входом стробирования вто" рого регистра, выходы разрядов левого и правого указателей которого соединены с вторыми входами элементов

И первой и второй групп соответствен5 но, выход третьего элемента И:соединен с вторыми входами элементов И третьей группы и первым входом первого элемента ИЛИ, выходы разрядов клю- jp ча записи второго:регистра соединены с первым входом элемента сравнения ,Р с и входами второго элемента ИЛИ,выход, которого. соединей с вторым входом р . ° второго элемента И и первым входом четвертого элемента И, выход которого является выходом отсутствия записи устройства, информационный вход третьего<" регистра .является входом ключа записи устройства, выход третьего регистра соединен с вторым входом элемента сравнения, выход.

"Равно" которого соединен с вторым входом третьего элемента И, выходы

6 В

"Меньще" и "Больше" элемента сравнения соединены с третьими входами элементов И первой и второй групп соот- ветственно, о т л и ч а ю щ е е с я тем, что, с целью упрощения; оно со" дер»кит два триггера и дифференцирующий элемент, прямой и инверсный вы". ходы первого триггера соединены с входом дифференцирующего элемента и вторым входом четвертого элемента

И, выход дифференцирующего элемента соединен с вторым входом первого элемента ИЛИ, инверсный. выход второгс» триггера является выходом готовности устройства, прямой выход второго триггера соединен с вторым входом первого элемента И, вход запуска устройства соединен с входом установки в "1" второго триггера, выход перво" го элемента ИЛИ соединен с входом сброса в "О" второго триггера, выход второго элемента И соединен с входом стробирования первого триггера.

1580396

AI I0I

А ЕМ

ЕОЗ

I04

Е05

I06

I07

I06

А4 Е09

ЕЕО

Ш

ЕЕ2.

II3

Аб- П4

ЕЕб

Ау= Пб

II7

А6= Пв

АЕ

А

Корень h

Аз

Фиг.3

Составитель В.Бородин

Редактор В.Данко Техред Л.Сердюкова Корректор С.Черни

Заказ 2014 Тираж 568 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Иосква, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул..Гагарина, 101