JPH038083A - 識別子付情報の木構造管理方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔概要〕 識別子付情報を木構造に登録して管理する木構造管理方
式に関し、 識別子付情報の識別子の各ピントによって左右ノードに
順次振り分けて木構造に登録し、識別子の登録順に影響
を受けることなく木構造にバランス良く登録すると共に
高速検索を可能にすることを目的とし、 識別子、右ポインタ、左ポインタ、および情報からなる
識別子付情報を木構造を構成する各ノードに持たせ、検
索しようとする識別子付情報の識別子の各ビットがＯＮ
／ＯＦＦに対応して木構造の頂点から初めて識別子付情
報の右ポインタ／左ポインタを順次辿り、該当する識別
子が見つかった場合にこれを検索対象の識別子付情報と
し、−方、見つからなかった場合にその旨、あるいは必
要に応じて終点の右ポインタ／左ポインタの先に新たな
識別子付情報を登録するように構成する。

〔産業上の利用分野〕

本発明は、識別子付情報を木構造に登録して管理する木
構造管理方式に関するものである。

（従来の技術と発明が解決しようとする課題〕各電報毎
に固有の識別子を持たせて情報管理を行う場合、例えば
４バイト整数型の識別子であれば−２３１ないし２３＋
　　１までの約４ギガ個の中から好みの値を選び、管理
することが可能である。

この際、各識別子毎に情報設定領域を初めから固定的に
持ったのでは多量となり、実現困難である。

このため、必要に応じて領域を確保し、各情報間をチエ
インし、管理することが行われている。

従来は第５図（イ）に示すように、識別子の大小関係に
よって左右のノードに振り分けて順次チェーンをはって
管理するようにしていた。このため、例えば識別子１２
．３・・・９９９．１０００というように昇順に登録し
ていくと、第５図（ロ）に示すように、一方向にしか振
り分けられないような事態が発生してしまい、１０００
個の情報を登録した状態で必要な情報を検索するのに最
大１０００回の検索が必要となってしまい、木構造が識
別子の登録の順序に依存してしまうというという問題が
あった。この一方向の振り分けを避けるには、バランス
をとりなおす操作が更に必要となってしまう問題があっ
た。

本発明は、識別子付情報の識別子の各ビットによって左
右ノードに順次振り分けて木構造にＧｉ！し、識別子の
登！３順に影響を受けることなく木構造にバランス良く
登録すると共に高速検索を可能にすることを目的として
いる。

（課題を解決する手段〕 第１図は、本発明の原理構成図を示す。

第１図において、識別子付情報１ば、識別子ｌ１１右ポ
インタ１−２、左ポインタ１−３、および情報１−４か
らなる木構造の各ノードに持たせるものである。

木構造は、識別子付情報１を２分木として登録したもの
である。

ｒ作用〕 本発明は、第１図に示すように、識別子１−１、右ポイ
ンタ１−２、左ポインタ１−３、および情Ｉ′１ｌｆ−
４からなる識別子付情１１１を木構造を構成する各ノー
ドに持たせ、検索しようとする識別子付情Ｉｔ１１の識
別子１−１の各ビットがＯＮ／ＯＦＦに対応して木構造
の頂点から初めて識別子付情報ｌの右ポインタ１−２／
左ポインタ１−３を順次辿り、該当する識別子１−１を
見つけた場合にこれを検索対象の識別子付情報ｌとし、
一方、見つけれなかった場合にその旨、あるいは必要に
応じて終点の右ポインタｌ−２／左ポインタ１−３の先
に新たな識別子付情報１を登録するようにしている。

従って、識別子付情６１の識別子１−１の各ビットのＯ
Ｎ／ＯＦＦによって左右のノードに振り分けて木構造を
順次検索して見つけたり、見つからないときに必要に応
じて登録したりすることにより、識別子付情報ｌの登ｉ
３順に影響を受けることなく、識別子付情報１を木構造
にバランス良く登録することが可能となると共に、高速
検索を行うことが可能となる。

〔実施例〕

次に、第１図から第４図を用いて本発明の１実施例の構
成および動作を順次詳細に説明する。

第１図において、゛ンリーの頂点ば、識別子付情報１を
ノードとして登録し、木構造を作成する場合の先頭の部
分である。

識別子付情報１は、図示のように、情報に付与する一意
の識別子１−１、当該識別子付情報１から右側のノード
（識別子付情報１）をポイントするポインタ（アドレス
）を格納する右ポインタ１−２、当該識別子付情報１か
ら左側のノード（識別子付情報１）をポイントするポイ
ンタ（アドレス）を格納する左ポインタ１−３、および
情ｆｉ１４から構成されるものである。

次に、第１図構成の動作を説明する。ここで、識別子１
−１を４ビツトとし、識別子付情ｌ［１１の識別子１−
１のビットが１のときに右に振るい分け（右ポインタ１
−２のポイント先に振るい分け）、ビットが０のときに
左に振るい分け（左ポインタ１−３のポイント先に振る
い分け）るようにする。例えば識別子“０１０１”の場
合頂点−左（０）−右（１）−左（０）−右（１） というように振るい分けると、図中斜線を引いた識別子
付ｍｆ１！１のように振るい分けられ、これらのうちの
いずれかに登録されることとなる。また、検索時には、
これら斜線を引いた識別子付悄ｆ［ｉｌのうちのいずれ
かとして見つけることができる。

尚、第１図は、模式的に判りやすく表したものであって
、実際には、第２図に示すように４ピントの識別子の場
合には、識別子付情ｆｌｉｔの総合計数は第２図に示す
ように１６個である。

第２図は、本発明の１実施例構成図を示す、これば、識
別子０、ｌ、２・・・１５（２進数で表すと識別子“ｏ
ｏｏｏ”　’０００１”００１Ｏ”・・・１１１１　”
）の順に登録した場合の木構造を示す、以下説明する。

ｆｉｌ　　ｍ刷子“００００”；フリーの頂点からポイ
ントされる最初の■識別子付情ｆＩ１１に識別子“ｏｏ
ｏｏ”を登録する。

（２）識別子“０００１″：フリーの頂点から初めて■
が既に登録されているため、■の位置で先頭のピントが
１０１であるため、左ポインタ１−３でポイントする■
識別子付情ＩＩＩに識別子°０００１１を登録する。

（３）識別子“００１０″：ツリーの頂点から初めて■
、■が既に登録されているので、■の位置で第２番目の
ビットが１０”であるため左ポインタ１−３でポイント
する■識別子付情報１に識別子“００１０”を登録する
。

（４）識別子“００１１″：ツリーの頂点から初めて■
、■、■が既に登録されているので、■の位置で第３番
目のビットが“１”であるため右ポインタ１−２でポイ
ントする■識別子付情報１に識別子“００１１”を登録
する。

（５）　　識別子“０１００°：フリーの頂点から初め
て■、■が既に登録されており、更に先頭から第２番目
のビットが“１“であるため、右ポインタ１−２でポイ
ントする■識別子付情ｆｇ１に識別子“０１００”を登
録する。

以下同様に、 （６）識別子“０１０１”は、左（０）−右（１）→左
（０）によって■に登録する。

＋７１　　識別子“０１１０”は、左（０）−右（１）
→右（１）によって■に登録する。

（８）識別子“０１１１”ば、左（０）−右（１）−右
（１）−右（１）によって■に登録する。

（９）識別子“ｔｏｏｏ”は、右（１）によって■に登
録する。

ａｏ　　識別子’１００１”は、右（１）−左（Ｏ）に
よって［株］に登録する。

αｒｊ　　識別子−１０１０’は、右（１）−左（Ｏ）
−右（１）によって■に登録する。

ａ３識別子’１０１１”は、右（１）→左（０）−右（
１）−右（１）によって＠に登録する。

０湯　識別子“１１００°ば、右（１）→右（１）によ
って０に登録する。

αＯ識別子’１１０１”は、右（１）→右（１）→左（
０）によって＠に登録する。

ａつ　　識別子’１１１０’は、右（１）−右（１）−
右（１）によって■に登録する。

０［９識別子“１１１１”は、右（１）−右（１）−右
（１）−右（１）によって［相］に登録する。

次に、第３図を用いて本発明の１実施例の構成の動作を
説明する。

第３図において、■は、ツリーの頂点の情報が設定され
ているアドレスを求める。

［相］は、Ｎ＝１と初期設定する。Ｎば、識別子の先頭
からのビット数を表す。

０ば、求めたアドレスの領域に情報が設定されているか
否かを判別する。ＹＥＳの場合には、［相］以降を実行
する。ＮＯの場合には、求めたアドレスの領域に識別子
が設定されていないので、登録無しと判定され（０）、
［相］で登録したいなら識別子付情ＩＩをここに設定す
る。例えば第２図ツリーの頂点からポイントされる■に
識別子が設定されていない場合には、ここに設定（登録
）する。

［相］は、探索する識別子と一敗か否かを判別する。

ＹＥＳの場合には、登録有りと判定され（０）、所望の
識別子付情報１が検索されたこととなる。

Ｎｏの場合には、［相］を実行する。

［相］は、検索する識別子のＮ番目のビットがＯＮ／Ｏ
ＦＦかを判別する。ＯＮの場合には０で左ポインタの内
容を求めたアドレスとし、ＹＥＳの場代には［相］で右
ポインタの内容を求めたアドレスとし、ともに■でＮ＝
Ｎ＋ＩＬ、■を実行する。

以上の処理によって、検索対象の識別子のビットによっ
て道順を振るい分けて木構造を順次探索し、所望のもの
を見つけることが可能となる。また、登録時には、見つ
からなかった終点の位置に当該登録しようとする新たな
識別子付情Ｗｉｌの識別子のビットによって道順を振る
い分けて登録する。

第４図は、本発明に係わるノード削除説明図を示す。

第４図（イ）は、削除対象の識別子Ｂの下に何もつなが
れていない場合を示す。この場合には、上側に記述する
識別子Ｂを削除し、下側に示すようにする。

第４図（ロ）は、削除対象の識別子Ｂの下に他の識別子
がつながれ、左側の識別子Ｅを優先して探すように設定
する場合を示す、この場合には、識別子Ｂを削除すると
共に、第４図（）Ｘ）に示すように、ｔｘＨａ別子Ａ刺
子ノードは削除する識別子Ｂの代わりに識別子Ｅを指す
、（２）識別子Ｅの左右ノードは識別子Ｂが持っていた
右ポインタおよび左ポインタを受は継ぐ、（３）識別子
Ｃの右ノー１′（右ポインタ）につながれていた情報Ｅ
をはずす。

第４図（ニ）は、第４図（／Ｘ）の状態のもとで、識別
子Ｅを削除し、左ノード（左ポインタ）にあるのを優先
して探すように設定する場合を示す。

この場合には、（Ｉ）　識別子Ａの右ノード（右ポイン
タ）は削除する識別子Ｅの代わりに識別子Ｃを指す、（
２）識別子Ｃの右／−ドは識別子Ｅが持っていたちのを
受は継ぐ。

〔発明の効果〕

以上説明したように、本発明によれば、識別子付情ＩＩ
の識別子１−１の各ビットのＯＮ／ＯＦＦによって左右
ノードに振り分けて木構造を順次検索して見つけたり、
見つからないときに登録したりする構成を採用している
ため、識別子１−１の登録順によって振るい分けが影響
を受けることなく、識別子付情ｌ１ＩＩを木構造にバラ
ンス良く登録することができると共に、このバランスの
良い木構造の識別子付情報ｌを順次辿って検索を高速に
行うことができる。これにより、木構造の管理情報数や
登録順序に処理速度が影響されることなく、管理するこ
とが可能となる。

例えば４バイト整数（−２”ないし２”−１）で表され
る４ギガ個の識別子の場合、検索処理に必要な最大回数
は、識別子のビット数をｍとすると、 となり、最大３３回の検索で識別子付情報１を見つける
ことができる。これだけの性能を、従来の第５図２分木
ソートの場合に必要なバランスを取り直すことなく、引
き出すことができる６

【図面の簡単な説明】

第１図は本発明の原理構成図、第２図は本発明の１実施
例構成図、第３図は本発明の動作説明フローチャート、
第４図は本発明に係わるノード削除説明図、第５図は従
来技術の説明図を示す。 図中、１は識別子付情報、１−１は識別子、１２は右ポ
インタ、１−３は左ポインタ、１−４は情報を表す。

Claims (1)

1. 【特許請求の範囲】 　識別子付情報を木構造に登録して管理する木構造管理
   方式において、 識別子（１−１）、右ポインタ、（１−２）、左ポイン
   タ（１−３）、および情報（１−４）からなる識別子付
   情報（１）を木構造を構成する各ノードに持たせ、検索
   しようとする識別子付情報（１）の識別子（１−１）の
   各ビットがＯＮ／ＯＦＦに対応して木構造の頂点から初
   めて識別子付情報（１）の右ポインタ（１−２）／左ポ
   インタ（１−３）を順次辿り、該当する識別子（１−１
   ）が見つかった場合にこれを検索対象の識別子付情報（
   １）とし、一方、見つからなかった場合にその旨、ある
   いは必要に応じて終点の右ポインタ（１−２）／左ポイ
   ンタ（１−３）の先に新たな識別子付情報（１）を登録
   するように構成したことを特徴とする識別子付情報の木
   構造管理方式。