Устройство для поиска информации
Изобретение относится к вычислительной технике. Целью изобретения является расширение функциональных возможностей устройства путем обеспечения нахождения записи с заданным ключом поиска в древовидной структуре с двоичным ветвлением . Устройство содержит группу элементов ИЛИ, регистр адреса, регистр информации, блок памяти, элемент ИЛИ, элемент задержки генератор тактовых импульсов, элемент И, узел сравнения, регистр ключа поиска , дешифратор, группы элементов И. 1 ил. о 9 ю о Од 00
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (19) (11) (5D 4 G 06 F 15/40
ОПИСАНИЕ ИЗОБРЕТЕНИЯ,., И АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3779884/24-24 (22) 09.08.84 (46) 23.01.86 ° Бюл. № 3 (72) Б.С ° Богумирский (53) 681.325(088.8) (56) Патент США ¹ 3909796, кл. 340-172.5, )975.
Авторское свидетельство СССР № 809206, кл. G 06 F 15/40, 1979, Авторское свидетельство СССР
¹ 1126972, кл. G 06 F 15/40, 1983. (54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ (57) Изобретение относится к вычислительной технике, Целью изобретения является расширение функциональных возможностей устройства путем обеспечения нахождения записи с заданным ключом поиска в древовидной структуре с двоичным ветвлением. Устройство содержит группу элементов ИЛИ, регистр адреса, регистр информации, блок памяти, элемент ИЛИ, элемент задержки, генера" тор тактовых импульсов, элемент И, узел сравнения, регистр ключа поиска, дешифратор, группы элементов И, 1 ил.
1206810
Изобретение относится к вычислительной технике и может быть использовано в системах управления базами данных.
Целью изобретения является расширение функциональных воэможностей путем обеспечения нахождения записи с заданным ключом поиска в древовидной структуре с двоичным ветвлением.
На чертеже приведена схема устройства.
Устройство содержит группу 1 элементов ИЛИ, регистр 2 адреса,. регистр 3 информации, разряды 4 данных, разряды 5 ключа, разряды 6 указателя, разряды 7 указателя регистра информации, блок 8 памяти, элемент ИЛИ 9, элемент 10 задержки, генератор 11 тактовых импульсов, элемент И 12,,узел 13 сравнения с выходами 14-16,регистр 17 ключа поиска, дешифратор 18, группы
19-21 элементов И, вход 22 запуска устройства, вход 23 ключа устройства, адресный вход 24 устройства, признаковый выход 25 и выход 26 устройства.
Бинарное дерево представляет собой древовидную структуру с двоичным ветвлением, в которой кажцый узел содержит данные и два указателя (один из указателей может быть пустым).
Каждый узел дерева занимает од ну ячейку блока 8 памяти и состоит из следующих полей: поля данных, поля ключа, поля левого указателя и поля правого указателя. Этим полям соответствуют групгы 4-7 разрядов регистра 3. Поиск записи (узла дерева1 осуществляется по ключу. Следовательно, каждый узел должен иметь уникальный ключ. Левый указатель узла определяет непосредственного потомка, ключ которого меньше ключа этого узла, а правый указатель определяет непосредственного потомка, ключ которого больше ключа этого узла. При отсутствии потомков в полях левого и/или правого указателя находится уникальный код, расшифровываемь и дешифратором 18.
Устройство работает следующим образом.
B исходном состоянии генератор
11 заторможен. По входу 24 в регистр
2 записывается адрес корневого узла дерева, а по входу 23 в регистр . 7
2S
ЗО
8Q 1
*.) 8
4) $ заносится ключ искомого узла !записи7. Устройство готово к работе.
Поиск информации инициируется подачей импульса по входу 22, в результате чего запускается -:.енератор !1. 1o импульсy с его выхода осуществляется прием корневого узла в регистр 3. В дальнеиыем в зависимости от соотношения между ключом искомой записи и ключом записи., находящейся в регистре 3, работа устройства может происходить следующими тремя путями.
Ключ считанной записи совпадает с ключом искомой записи. В этом случае появляется сигнал на выходе
16 узла 13., подготаьливающий к срабатыванию элемент И 12. При появлении импульса на выходе элемента 10 задержки сра" àòûâàåò элемент И 12, в результате чего искомая запись (поле данных) через группу 21 элементов И поступает на выход 26 устройства, а генератор 11 останавливается.
Ключ считанной записи меньше клю— ча искомой записи. При этом появляется сигнал на выходе 14 узла 13, подготавливаюший к открытию группу
20 элементов И, По импульсу с выхода элемента 10 задержки открывается группа 20 элементов 11 и правый указатель из группы 7 разрядов регистра 3 переписывается в регистр 2.
По второму импульсу с выхода генератора 11 в регистр 3 будет принят правый непосредственный потомок корневого узла. ключ которого анализируется таким же образом.
Ключ считанной записи больше ключа искомой записи. В этом случае появляется сигнал на выходе !5 у-зла 13, ко": îðûé подготавливает к открытию группу 19 элементов И. По импульсу с выхода элемента !О задержки открывается группа 19 элементов И и левый указатель из группы 6 разрядов регистра 3 переписывается в регистр 2. По второму импульсу с выхода генератора 11 в регистр 3 принимается левый непосредственный потомок корневого узла,, ключ которого анализируется таким же образом.
В дальнейшем устройство работает аналогично. Следующим после очередного узла. выбирается левый или правый непосредственный его потомок в
3 1 зависимости от результатов сравнения его ключа с ключом искомой записи.
При попытке записи в регистр 2 пустого указателя появляется импульс на выходе дешифратора 18. Этот импульс проходит на выход 25 устройства, сигнализируя об отсутствии в дереве искомой записи,а также оста навливает генератор 11.
Известное устройство предназначено главным образом для поиска записи по ключу в таблице фиксированного размера, так как последовательное упорядоченное по ключам расположение записей делает вставки и удаления записей трудоемкими, что затрудняет модификацию таблицы, Если таблица динамически изменяется, то экономия по времени от использования поиска в отсортированной таблице не покроет затрат на поддержание упорядоченного расположения ключей. !
Рассмотренное устройство осуществляет поиск записи в бинарном дереве. Использование структуры бинарного дерева позволяет быстро вставлять и удалять записи, меняя только указатели и не перемещая записи. Количество обращений к памяти остается равным log Формула и з о б р е т е н и я Устройство для поиска информации, содержащее группу элементов ИЛИ, регистр адреса, регистр информации, блок памяти, элемент ИЛИ, элемент задержки, генератор тактовых импульсов, элемент И, узел сравнения, регистр ключа поиска, дешифратор и три группы элементов И, причем вход запуска устройства соединен с входом запуска генератора тактовых импульсов, выход которого соединен с входом элемента задержки, выходы элементов И первой и второй групп соедине206810 45 ны соответственно с первыми и вторыми входами элементов ИЛ11 группы, первый и второй выходы неравенства узла сравнения соединены соответственно с первыми входами элементов И первой и второй групп, вход признака поиска устройства являетСя входом регистра ключа поиска, выход которого подключен к первому входу узла сравнения, второй вход которого соединен с выходами разрядов ключа регистра информации, информационный -вход которого соединен с выходом блока памяти, адресный вход которого соединен с выходом регистра адреса, выход дешифратора соединен с первым входом элемента ИЛИ, выход которого соединен с входом генератора импульсов, выход равенства узла срав— нения подключен к первому входу элемента И, о т л и ч а ю щ е е с я тем, что, с целью расширения ее функциональных воэможностей путем.обеспечения нахождения записи с заданным ключом поиска в древовидной структуре с двоичным ветвлением, в нем адресный вход устройства соединен с третьими входами элементов ИЛИ группы, выход дешифратора подключен к признаковому выходу устройства, выходы элементов ИЛИ группы соединены с входами дешифратора и регистра адреса, выход генератора тактовых импульсов соединен с синхронизирующим входом регистра информации, выходы разрядов данных которого соединены с первыми входами элементов И третьей группы, вторые входы которых и второй вход элемента ИЛИ соединены с выходом элемента И, выход элемента задержки соединен с вторым входом элемента И и с вторыми входами элементов И первой и второй групп, третьи входы которых подключены соответственно к выходам разрядов первого и второго указателей регистра информации, выходы элементов И третьей группы являются выходом устройства. 12068!О Составитель A.Æåðeíîâ Техред Т.Дубинчак Корректор Т.Колб Редактор П.Коссей Тираж 673 Подписное ЙНИИПИ Гасударственного комитета СССР по дел:ам изобретений и открытий 113035, Москва., Б-35, Раушская наб., д. 4/5 Эаказ 8715/51 Филиал ППП "Патент", г. Ужгород, ул.. Проектная, 
