Устройство для поиска информации Советский патент 1986 года по МПК G06F17/30 

1

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

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

На чертеже приведена схе;ма устройства.

Устройство содержит группу 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. Поиск записи (узла дерева) осуществляется по ключу. Следовательно, каждый узел должен имет уникальный ключ. Левый указатель узла определяет непосредственного потомка, ключ которого меньше ключа этого узла, а правый указатель определяет непосредственного потомка, ключ которого бопъюе ключа этого узла. При отсутствии потом:ков в полях левого и/или правого указателя находится уникальный код, расшифровываемый дешифратором 8.

Устройство работает следующим образом.

В исходном состоянии генератор 11 заторможен. По входу 24 в регист 2 записывается адрес корневого узла дерева, а по входу 23 в регистр з7

2068ЛО2

заносится ключ искомого узла (запи- си). Устройство готово к работе. Поиск информации инициируется подачей импульса по входу 22, в 5 результате чего запускается генератор 11. По первому рмпульсу с его выхода осуществляется прием корневого узла в регистр 3, В дальнейшем в зависимости от соотношения ме/кду 10 ключом искомой записр и ключом записи., Находящейся в регистре 3, работа устройства может происходить следующими тремя путями.

101ЮЧ считанной записи совпадает с ключом искомой записи, В этом случае появляется сигнал на выходе 16 узла 13.J подготавливающий к срабатыванию элемент И 12. При появлении 1 1мпульса на выходе элемента 10 задержки срабатывает элемент И 12, в результате чего искомая запись (поле данных) через группу 21 элементов И поступает на выход 26 устройства, а генератор 11 останавливается.

Ключ считанной записи меньше ключа искомой записи. При этом появляется сигнал на выходе 14 узла 13, подготавливающий к открытию группу 20 элементов И. По импульсу с выхода элемента 10 задержки открывается группа 20 элементов И и правый указатель из группы 7 разрядов регистра 3 переписывается в регистр 2. По второму импульсу с выхода генератора 11 в регистр 3 будет принят правый непосредственный потомок корневого узла, ключ которого а 1ализи- руется таким же образом.

Ключ считанной записи болыле ключа искомой записи, В этом случае

появляется сигнал на выходе 15 узла 13, который подготавливает к открытию группу 19 элементов И, По импульсу с выхода элемента 10 задержки открывается группа 19 элементов И и левый указатель из группы 6 разрядов регистра 3 переписывается в регистр 2. По второму импульсу с выхода генератора 11 в регистр 3 приньшается левый непосредственный потомок корневого узла5 ключ которого анализируется таким же образом,

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

зависимости -от результатов сравнения его ключа с ключом искомой записи.

При попытке записи в регистр 2 пустого указателя появляется импульс на выходе дешифратора 8. Этот импульс проходит на выход 25 .устройства, сигнализируя об отсутствии в дереве искомой записи,а также оста навливает генератор 11.

Известное устройство предназначено главным образом для поиска записи по ключу в таблице фиксированного размера, так как последовательное упорядоченное по ключам расположение записей делает вставки и удаления записей трудоемкими, что затрудняет модификацию таблицы. Если таблица динамически изменяется, то зкономия по времени от использования поиска в отсортированной таблице не покроет затрат на поддержание упорядоченного расположения ключей.

Рассмотренное устройство осуществляет поиск записи в бинарном дереве. Использование структуры бинарного дерева позволяет быстро вставлять и удалять записи, меняя только указатели и не перемещая записи. Количество обращений к памяти остается равным , где Н - число записей в наборе данных.

Формула изобретения

Устройство,для поиска информации, содержащее группу элементов ИЛИ, регистр адреса, регистр информации, блок памяти, элемент ИЛИ, элемент задержки, генератор тактовых импульсов, элемент И, узел сравнения, регистр ключа поиска, дешифратор и три группы элементов И, причем вход запуска устройства соединен с входом запуска генератора тактовых импульсов, выход которого соединен с вхо- ;дом элемента задержки, выходы элементов И первой и второй групп соедине06810

ны соответственно с первыми и вторыми входами элементов 1-1ГП1 группы, первый и второй выходы неравенства узла сравнения соединены соответственно 5 с первыми сходами элементов И первой и второй групп, вход признака поиска устройства является входом регистра ключа поиска, выход которого подключен к первому входу узла

10 сравнения, второй вход которого соединен с выходами разрядов ключа регистра информации, информационньй вход которого соединен с выходом блока памяти, адресный вход которо15 го соединен с выходом регистра адреса, выход дешифратора соединен с первым входом элемента ИЛИ, выход которого соединен с входом г.енератора импульсов, выход равенства узла срав20 нения подключен к первому входу эле- мента И, отличающееся тем, что, с целью расширения ее функциональных возможностей путем- обеспечения нахождения записи с задан25 ным ключом поиска в древовидной , структуре с двоичнь М ветвлением, в нем адресный вход устройства соединен с третьими входами элементов ИЛИ группы, выход дешифратора под30 ключен к признаковому выходу устройства, выходы элементов ИЛИ группы соединены с входами дешифратора и регистра адреса, выход генератора тактовых импульсов соединен с синхро- НИЗИРУЮ1ДИМ входом регистра информации, выходы разрядов данных которого соединены с первыми входами элементов И третьей группы, вторые входы которых и второй вход элемента ИЛИ соединены с выходом элемента И, выход элемента задержки соединен с вторым входом элемента И и с вторыми входами элементов И первой и второй групп, третьи входы которых подключены соответственно к выходам разрядов первого и второго указателей регистра информ§1ции, выходы элементов И третьей группы являются выходом устройства.

35

40

45

2S

Составитель А.Жеренов Редактор П.Коссей Техред Т.Дубинчак Корректор Т.Колб

Заказ 8715/51 Тираж 673Подписное

Й1ИИ11И Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП Патент, г, Ужгород, ул.. Проектная, 4

a flL

Изобретение относится к вычислительной технике. Целью изобретения является расширение функциональных возможностей устройства путем обеспечения нахождения записи с заданным ключом поиска в древовидной структуре с двоичным ветвлением. Устройство содержит группу элементов ИЛИ, регистр адреса, регистр информации, блок памяти, элемент ИЛИ, элемент задержки генератор тактовых импульсов, элемент И, узел сравнения, регистр ключа поиска, дешифратор, группы элементов И. 1 ил. о 9 ю о Од 00