ローテーションに基づく2分木間の距離
スポンサーリンク
概要
- 論文の詳細を見る
木の近さや類似性に関する閥題は、パターン認識や誤り訂正構文解析などに関連して検討されてきた。この近さや類似性を表す尺度が距離であり,一般には重み付きレーベンシュタイン距離で定義されている(文献1)。本報告では,木のトポロジ(位相)を意識した距離として,ローテーション(回転)に基づく2分木の距離を考える。ローテーションは,木をデータ構造としてとらえたとき,見出し(キー)の挿入や削除にともなう更新のための基本的技法である。同じ大きさの2分木AとBがあるとき,AからBへ変換するローテーションの最小数を距離とする。とくに,木Aと木Bの距離が1のとき,この2つの木は結合しているという。まず,2分木をコードワードとよばれる整数列で表現し,その辞書式順序に基づいて2分本のランク(番号)付けを行う。つぎに,大きさnの2分木にたいして,ランクを要素とする結合表を作成する。2分木間の距離はこの結合表をもとにしたグラフから,単純な最短経路問題として求めることができる。
- 一般社団法人情報処理学会の論文
- 1991-02-25
著者
関連論文
- L5009 大学生による講義評価に影響を及ぼす諸要因についてIV
- 映進対称性を持つフラクタル・テクスチュアパターンの生成
- Coloring of Polytopes in Four Dimensions
- 5D-2 文字図形にたいする細線化アルゴリズムの提案と評価
- 視覚障がい者のためのペン入力触覚ガイドを用いた二次元配列位置情報の入力手法の改良と評価(福祉情報工学,ヒューマンコミュニケーション〜人間中心の情報環境構築のための要素技術〜論文)
- 地域学校共同データベースを中心として構築したシステムの運用と評価(教育情報の解析と数理モデル/一般)
- (101)教育情報のデータベース化について : イントラネットの教育現場への適用(第25セッション CAI・マルチメディア(V))
- 地域学校共同運用データベースの構築 : イントラネットの考え方を応用したシステム
- WWWを利用した地域学校共同運用データベースの構築
- コンピュータ・アニメーションを利用した手話教育システム構築の試み
- 触覚と聴覚を利用した視覚障がい者用図形入力インタフェースにおける入力支援
- 触覚と聴覚を利用した視覚障がい者用図形入力インタフェースにおける入力支援(高齢者の認知機能保障技術及び一般)
- 長野県短期大学における2006年度新入生のパソコン利用状況に関する調査
- 教養学科における情報処理演習の変遷 : MS-DOSからWindowsへ、そしてWWWの利用(総合科学系)
- パソコン演習における日本語入力操作の習熟過程
- 表計算ソフトの基礎知識にたいする一教材とその実践
- 2分木の符号化とその応用
- ロ-テ-ションの回数に基づく2分木間の距離
- 地域における情報通信の動向
- Lotus1-2-3をもちいた入試処理
- 教養学科における情報処理教育
- LEFTIST木の総数にたいする一評価
- 聴覚ディスプレイとペン入力触覚ガイドを用いた視覚障害者用GUI支援システム
- タブレット入力と仮想音響出力を有する視覚障害者用図形伝達システムにおけるペン入力ガイドの改良(ヒューマンコミュニケーショングループ (HCG) シンポジウム)
- 積極的なタイピング練習を行わないときの日本語入力操作の特徴 : 短大におけるコンピュータ・リテラシー教育の事例
- 表計算ソフト習得上の問題点の分析
- 文系女子短大におけるパソコン・リテラシー教育の企画・実践・評価 - 長野県短期大学教養学科の事例 -
- コンピュ-タ動作理解のための教育支援システム--その教材としての評価
- ローテーションに基づく2分木間の距離
- ビットストリングによる2分木の表現
- 視覚障害者のための音の移動感を用いた線形図形の生成による図形教育への応用
- パソコン演習における日本語入力操作の習熟過程