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

СОЮЗ СОВЕТСНИХ,СОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 09) 00 СИ) С 06 Р 15 40 ОПИСАНИЕ ИЗОБРЕТЕНИЯН АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЦТИЯМПРИ ГННТ СССР 1(56) Авторское свидетельство СССРФ 1206810, кл, С 06 Р 15/40, 1984.,Авторское свидетельство СССРВ 1325514, кл. С 06 Г 15/40, 1986,(54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМА 1 И (57) Изобретение относится к вычислительной технике и может быть использовано в системах управления базами данных. ель изобретения - упрощение устройства. Устройство содержит регистр 1, элемент И 3, элемент 15 задержки, генератор 19 импульсов, группы 2, 13 и 14 элементов И, группу 10 элементов ИЛИ, регистр 11, элемент 4 сравнения,.регистр 5, блок 12. памяти, триггеры и элементы ИЛИ, Устройство обеспечивает поиск записи с заданным ключом с любого адреса исходного массива, представляющего собой бинарную древовидную структуру, в которой каждая запись сопровождается, кроме того, левым и правым указателями. В полях указателей узлов бинарного дерева, не имеющих непосредственных потомков, содержится ссылка на ко" рень. Если поиск начинается с левого поддерева записи, находящейся в правом поддереве, то производится нахождение корня, а затем переход в правое поддерево. При отсутствии записи процедура поиска обеспечивает двойное прохождение корня, на основе которого формируется сигнал "Отсуттвие записи". 3 ил.45 Изобретение относится к вычислительной технике и может быть использовано в системах управления базамиданных.Цель изобретения - упрощение устройства.На фиг, показана структурная схема устройства; на фиг.2 - пример бинарного дерева; на фиг.3 - его разме Ощение в блоке памяти,Устройство содержит регистр 1,группу 2 элементов И, элемент И 3,элемент 4 сравнения, регистр 5,включающий поле 6 данных, поле 7 ключа 15записи, поле 8 адреса левого указателя, поле .9 адреса правого указателя, группу 10 элементов ИЛИ, регистр11, блок 12 памяти, группы 13 и 14элементов И, элемент 15,задержки, 20элемент ИЛИ 16 с инверсным выходом,элемент И 17, элемент И 18, генератор 19 импульсов, триггер 20, элементИ 21, триггер 22, элемент ИЛИ 23,дифференцирующий элемент 24, выход 2525 "Равно-", выход 26 "Меньше" и выход 27 "Больше" элемента 4, вход 28адреса устройства, выход 29 готовности устройства, вход 30 запуска устройства, выход 31 "Отсутствие записи" устройства, вход 32 ключа устройства, информационный выход 33 устройства.Рассмотрим принципы построенияи работу устройства.35Устройство предназначено для поиска информации со структурой бинарного дерева. Для организации бинарногодерева каждая ячейка памяти содержитчетыре поля: ключа, левого указателя, 40правого указателя и данных. В полеключа содержится идентификатор записей поля данных. Поле левого указателя содержит адрес ячейки памяти,где размещаются данные, ключ которых меньше, а в поле правого указателя - адрес ячейки памяти с данными,у которых ключ больше этого ключа.Пусть необходимо разместить вполе памяти данные с идентификаторами, значения которых лежат в пределахчисел натурального ряда от 1 до 18.Бинарное дерево для данного случаяпоказано на фиг,2. Оно содержит узлы,где цифрами указано значение ключа,55а знаками ( иотмечены поле левого и правого указателей. Узел сключом, равным 9, является корнемдерева. Узлы с ключами от 1 до 8 образуют левое дерево, а узлы с ключами от О до 18 - правое поддерево.Узлы, не имеющие левого или правого .указателя, помечаются ссылкой наадрес ячейки, где размещен адрес корневого узла,Пример отображения дерева на память показан на фиг.3, где слева указаны адреса ячеек памяти с 101 по119. Адресом корня является адрес,равный 109. Этот адрес размещается вузлах, не имеющих указателей,Пусть необходимо сосчитать данные, ключ которых равен 16.Исходное/состояние устройства характеризуется тем, что триггеры 20 и 22 установлены в состояние "0" (не показано).По входу 28 через элементы ИЛИ 10в регистр 11 записывается начальныйадрес дерева А= 101, а по входу332 в регистр 1 - ключ искомого узла(записи) Клд= 16.Поиск данных инициируется подачейсигнала пуска по входу 30. По этомусигналу триггер 22 устанавливается в"1", открывая элемент И 17. По первому импульсу генератора 19 осуществляется прием содержимого ячейкис адресом 101 в регистр 5.Так как ключ в регистре 1 большесчитанного ключа в поле 7 регистра 5(161), то на выходе 27 "Больше"элемента 4 формируется единичный сигнал, по которому открываются элементыИ 13. При появлении импульса на выхо.де элемента 15 задержки адрес правогоуказателя из поля 9 регистра 5 через элементы И 13 и ИЛИ 10 передается в регистр 11, где устанавливается адресА = 102.Время задержки элемента 15 определяется временем переходных процессовв регистре 5 и элементе 4 сравнения.После чтения информации в регистре 5КлКП з (162) и рассмотреннымпорядком в регистр 5 принимается информация по адресу 119, Так как ключэтого узла равен нулю, то на выходе27 "Больше" удерживается единичныйсигнал, по которому в регистр 5 считывается информация по корневому узлу.В дальнейшем поиск данных продолжается в правом поддереве в соответствии с рассмотренным с последовательным формированием адресов А, АиА,Когда в регистре 5 находится информация с корневого узла, на выходеэлемента 4 удерживается единичный сигнал, по которому определяется передача адреса корня А т в регистр 11.После приема информации в регистр 5 из ячейки с А т119 на выходе поля 7 устанавливаются нулевые сигналы (Клэ = О). При этом на выходе элемента ИЛИ 16 формируется единичный сигнал, открывающий элемент И 18Задержанным импульсом с выхода эле"мента 15 задержки триггер 20 устанавливается в нулевое состояние. С помощью дифференцирующего элемента 24 формируется импульс, которым через элемент ИЛИ 23 триггер 22 устанавливается в нулевое состояние. Таким образом, на выходах 29 и 31 установлены единичные сигналы, что свидетельствует об отсутствии записи с заданным ключом (Кл= 9) в блоке 12 памяти.Поиск записи с ключом, находящимся в левом поддереве, осуществляется аналогично рассмотренному, но без перехода через корень в правое поддерево, если поиск начинается с начального адреса А . Формула 30 Устройство для поиска информации, содержащее группу элементов ИЛИ, ":ри группы элементов И, блок памяти, три регистра, элемент сравнения четыре элемента И, элемент задержки, генератор импульсов и два элемента ЮИ, выход генератора импульсов соединен с первым входом первого элемента И,выход которого через элемент задержкисоединен с первыми входами элементовИ первой н второй групп и первымивходами второго и третьего элементов И, первые входы элементов ИЛИ группы являются адресным, входом устройства, выходы элементов И первой и второй групп соединены с вторыми и третьими входами элементов ИЛИ группысоответственно, выходы элементов ИЛИ группы соединены с информационными входами первого регистра, выходкоторого соединен с адресным входомблока памяти, выход которого соединенс информационным входом второго регистра, выходы разрядов данных кото" ментов И третьей группы, выходы которых являются информационными выходамиустройства, выход первого элемента 35 1580396 6элемента ИПИ 16 формируется единичный сигйал (так как КЛ 5О), открывающий элемент И 18. Задержанный им. пульсом генератора 19 с выхода элемента 15 задержки через элемент И 18устанавливается по счетному входув "1" триггер 20.От момента приема информации в регистр 5 до момента установки триггера 20 в единичное состояние при данной ситуации на выходе 31 "Отсутствие записи" формируется единичныйсигнал. Но так как триггер 22 находится в единичном состоянии, то навыходе 29 сигнал готовности устройства к чтению отсутствует. Поэтомуединичный сигнал на выходе 31 неФпринимается во внимание,Когда в регистре 11 окажется информация, сосчитанная по адресу А =118, на выходе 26 "Меньше" элемента 4 формируется единичный сигнал,так как Кл ( КЛ(16 ( 18), Даннымсигналом определяется передача адреса А, = 116 из поля 8 регистра 5через элементы И 14 и ИЛИ 10 в регистр 11,После приема информации в регистр11 из ячейки с А= 116 на первом изобретенияи втором входах элемента 4 устанавливаются одинаковые ключи (Кл= Кл ).При этом на выходе 25 "Равно" зле -мента 4 формируется единичный сигнал,по которому данные из поля 6 регист 35ра 5 передаются на выход 33 через элементы И 2 по задержанномуимпульсу,проходящему через открытый в данном. случае элемент И 3. Этим же сигналом через элемент ИЛИ 23 триггер 22 40устанавливается в нулевое состояние,Единичный сигнал с единичного выходатриггера 22 подается на выход 29 ииспользуется в качестве сигнала готовности устройства к чтению. Так как 45на выходе 31 сигнал отсутствует,топроизводится обращение к устройствуза данными, передаваемыми на выход33 через элементы И 2.Пусть требуется сосчитать данные, 50ключ которых равен 19. Для этогоустройство приводится к исходному состоянию и запускается сигналомпуска по входу 30. Работа устройства при формировании в регистре 11 55адресов А - А аналогична рассмот- рого соединены с первыми входами элеренной.Когда в регистре 11 окажется адрес А= 118, на выходе 27 "Больше"7 158039 И соединен с входом стробирования вто" рого регистра, выходы разрядов левого и правого указателей которого соединены с вторыми входами элементов И первой и второй групп соответствен 5 но, выход третьего элемента И соединен с вторыми входами элементов И третьей группы и первым входом первого элемента ИЛИ, выходы разрядор клю О . ча записи второго:регистра соединены с первым входом элемента сравнения Рси входами второго элемента ИЛИ,выход, которого. соединей с вторым входом р . Ф.второго элемента И и первым входом четвертого элемента И, выход которого является выходом отсутствия записи устройства, информационный вход третьегог, регистра .является входом ключа записи устройства, выход тре О тьего регистра соединен с вторым входом элемента сравнения, выход. "Равно" которого соединен с вторым входом третьего элемента И, выходы 6 В"Меньще" и "Больше" элемента сравнения соединены с третьими входами элементов И первой и второй групп соот-ветственно, о т л и ч а ю щ е е с ятем, что, с целью упрощения; оно со"дерзит два триггера и дифференцирующий элемент, прямой и инверсный вы",ходы первого триггера соединены свходом дифференцирующего элементаи вторым входом четвертого элементаИ, выход дифференцирующего элементасоединен с вторым входом первого элемента ИЛИ, инверсный. выход второгстриггера является выходом готовностиустройства, прямой выход второготриггера соединен с вторым входомпервого элемента И, вход запуска устройства соединен свходом установкив "1" второго триггера, выход перво"го элемента ИЛИ соединен с входомсброса в "0" второго триггера, выходвторого элемента И соединен с входомстробирования первого триггера.1580396 О 10108 9 К 4 4 б л 19 АЗ Составитель В.Боро Техред Л. Сердюкова Корректор С.Черни Редактор В.Даик Тираж 568енного комитета по и 13035, Иосква, Ж,аказ 2014НИИПИ Государст Подписно иям при ГКНТ ССС обретениям и отк Раушская наб., д льский комбинат "Патент", г. Ужгород, улГагарин водственно-и да А 1 л 101 А 2 1% 103 104