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

(57) Изобрет лительной те ие относи ся кизобфункройстения ке, Цель сширение ия являетсяальных возмоутем обеспечзаданным кл ностеи усния нахожд 796,м поиска в виднои структуре с двоичным ветвлением. Устройство содержит группуэлементов ИЛИ, регистр адреса, регистр информации, блок памяти, элемент ИЛИ, элемент задержки, генера"тор тактовых импульсов, элемент И,узел сравнения, регистр ключа поиска, дешифратор, группы элементов И,ьство СССР15/40, 1979,ьство СССР15/40, 1983 54) УСТРОЙ ОИСКА РМА ил. ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬТИ ОПИСАНИЕ ИЗОБ АВТОРСКОМУ СВИДЕТЕЛЬИзобретение относится к вычислительной технике и может быть использовано в системах управлениябазами данных.Целью изобретения является расширение Функциональных воэможностейпутем обеспечения нахождения записи с заданным ключом поиска в древовидной структуре с двоичным ветвлением.На чертеже приведена схема устройства.Устройство содержит группу 1элементов ИЛИ, регистр 2 адреса,.регистр 3 инФормации, разряды 4данных, разряды 5 ключа, разряды буказателя, разряды 7 указателярегистра инФормации, блок 8 памяти,элемент ИЛИ 9, элемент 10 задержки,генератор 11 тактовых импульсов,элемент И 12 узел 13 сравнения свыходами 14-16,регистр 17 ключапоиска, дешиФратор 18, группы19-21 элементов И, вход 22 запуска устройства, вход 23 ключа устройства, адресный вход 24 устройства, признаковый выход 25 и выход 26устройства.Бинарное дерево представляет собой древовидную структуру с двоичным ветвлением, в которой кажцыйузел содержит данные и два указателя (один из указателей может бытьпустым).Каждый узел дерева занимает одну ячейку блока 8 памяти и состоитиз следующих полей; поля данных, поля ключа, поля левого указателя иполя правого указателя, Этим полямсоответствуют групгы 4-7 разрядоврегистра 3, Поиск записи узла дерева) осуществляется по ключу. Следовательно, каждый узел должен иметьуникальный ключ. Левый указатель узла определяет непосредственногопотомка, ключ которого меньше ключаэтого узла, а правый указатель определяет непосредственного потомка,ключ которого больше ключа этогоузла. При отсутствии потомков в полях левого и/или правого указателянаходится уникальный код, расшиФровываемый дешиФратором 18,Устройство работает следующимобразом.В исходном состоянии генератор11 заторможен. По входу 24 в регистр2 записывается адрес корневого узладерева, а по входу 23 в регистр .7206810заносится ключ искомого узла записи 7, Устройство готово к работе,Поиск инФормации инициируетсяподачей импульса по входу 22, в результате чего запускается генератор 1, По первому импульсу с его выхода осуществляется прием корневого узла в регистр 3. В дальнеиыем в зависимости от соотношения между ключом искомой записи и клю том записи находящейся в регистре 3, работа устройства может происходитьследующими тремя путями. 2 О 25 ЗО 35 ,)О 4)Ключ считанной записи совпадаетс ключом искомой записи, 8 этомслучае появляется сигнал на выходе16 узла 13 подготаьливающий к срабатыванию элемент И 2. При появлении импульса на выходе элемента 10задержки срабатывает элемент И 12,в результате чего искомая запись1,поле данных) через группу 21 элементов И поступает на выход 26 устройства, а генератор 11 останавливается.Ключ считанной записи меньше клю -ча искомой записи, При этом появляется сигнал на выходе 14 узла 13,подготавливаюший к открытию группу20 элементов И, По импульсу с выхода элемента 10 задержки открываетсягруппа 20 элементов И и правый указатель из группы 7 Разрядов регистра 3 переписывается в регистр 2.По второму импульсу с выхода генератора 11 в Регистр 3 будет принятправый непосредственный потомок корневого узла. ключ которого анализируется таким же образом,Ключ считанной записи дольше ключа искомой записи. В этом случаепоявляется сигнал на выходе 5 у.зла 13, который подготавливает к открытию группу 19 элементов И, Поимпульсу с выхода элемента О задержки открывается группа 9 элементов И и левый указатель из группы 6разрядов регистра 3 переписываетсяв регистр 2. По второму импульсу свыхода генератора 11 в регистр 3принимается левый непосредственныйпогомок корневого узла ключ которого анализируется таким же образом,В дальнейшем устройство работаетаналогично. Следующим после очередного узла. выбирается левый или правый непосредственный его потомок в3 1зависимости от результатов сравнения его ключа с ключом искомой записи.При попытке записи в регистр 2пустого указателя появляется импульс на выходе дешифратора 18. Этотимпульс проходит на выход 25 устройства, сигнализируя об отсутствиив дереве искомой записи,а также останавливает генератор 11,Известное устройство предназначено главным образом для поиска записи по ключу в таблице фиксированного размера, так как последовательноеупорядоченное по ключам расположениезаписей делает вставки и удалениязаписей трудоемкими, что затрудняетмодификацию таблицы, Если таблицадинамически изменяется, то экономияпо времени от использования поискав отсортированной таблице не покроет затрат на поддержание упорядоченного расположения ключей,Рассмотренное устройство осуществляет поиск записи в бинарном дереве. Использование структуры бинарного дерева позволяет быстро вставлять и удалять записи, меняя только указатели и не перемещая записи. Количество обращений к памяти остается равным Ход И, где И - число записей в наборе данных.Формула изобретенияУстройство для поиска информации, содержащее группу элементов ИЛИ, регистр адреса, регистр информации, блок памяти, элемент ИЛИ, элемент задержки, генератор тактовых импульсов, элемент И, узел сравнения, регистр ключа поиска, дешифратор и три группы элементов И, причем вход запуска устройства соединен с входом запуска генератора тактовых импульсов, выход которого соединен с входом элемента задержки, выходы элементов И первой и второй групп соедине 20 б 810 5 1 О 15 20 25 30 35 40 45 ны соответственно с первыми и вторыми входами элементов ИЛ 11 группы, первый и второй выходы неравенства узласравнения соединены соответственнос первыми гходами элементов И первой и второй групп, вход признакапоиска устройства являетСя входомрегистра ключа поиска, выход которого подключен к первому входу узласравнения, второй вход которогосоединен с выходами разрядов ключарегистра информации, информационныйвход которого соединен с выходомблока памяти, адресный вход которого соединен с выходом регистра адреса, выход дешифратора соединен с первым входом элемента ИЛИ, выход которого соединен с входом генератораимпульсов, выход равенства узла сравнения подключен к первому входу элемента И, о т л и ч а ю щ е е с ятем, что, с целью расширения ее функциональных воэможностей путем обеспечения нахождения записи с заданным ключом поиска в древовиднойструктуре с двоичным ветвлением, внем адресный вход устройства соединен с третьими входами элементовИЛИ группы, выход дешифратора подключен к признаковому выходу устройства, выходы элементов ИЛИ группысоединены с входами дешифратора ирегистра адреса, выход генераторатактовых импульсов соединен с синхронизирующим входом регистра информации, выходы разрядов данных которого соединены с первыми входами элементов И третьей группы, вторые входы которых и второй вход элементаИЛИ соединены с выходом элемента И,выход элемента задержки соединенс вторым входом элемента И и с вторыми входами элементов И первой ивторой групп, третьи входы которыхподключены соответственно к выходам разрядов первого и второго указателей регистра информации, выходыэлементов И третьей группы являютсявыходом устройства.12068 О Составитель Техред Т.Ду Жерехнчак едактор П.Косс орректор Т.Кол аказ 87 ого к ии и 5 кая наб. илиал ППП "Патент", г. Ужгород, ул. Проектная,Тираж б 73 ЙНИИПИ Государственн по делам изобрете 5, Москва., Б, Рау