論文の概要: An Extended Symbolic-Arithmetic Model for Teaching Double-Black Removal with Rotation in Red-Black Trees

• arxiv url: http://arxiv.org/abs/2504.03259v1
• Date: Fri, 04 Apr 2025 08:19:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-07 14:47:32.580317
• Title: An Extended Symbolic-Arithmetic Model for Teaching Double-Black Removal with Rotation in Red-Black Trees
• Title（参考訳）: 赤黒木における回転を伴う二重黒除去指導のための拡張的シンボリック・アリートメティクスモデル
• Authors: Kennedy E. Ehimwenma, Hongyu Zhou, Junfeng Wang, Ze Zheng,
• Abstract要約: ダブルブラック(DB)ノードは、レッドブラック(RB)ツリーにはない。 他の連結ノードの回転と再色を引き起こすDBノードの除去は、RBツリーの教育と学習において大きな課題となる。
• 参考スコア（独自算出の注目度）: 14.338255658390104
• License:
• Abstract: Double-black (DB) nodes have no place in red-black (RB) trees. So when DB nodes are formed, they are immediately removed. The removal of DB nodes that cause rotation and recoloring of other connected nodes poses greater challenges in the teaching and learning of RB trees. To ease this difficulty, this paper extends our previous work on the symbolic arithmetic algebraic (SA) method for removing DB nodes. The SA operations that are given as, Red + Black = Black; Black - Black = Red; Black + Black = DB; and DB - Black = Black removes DB nodes and rebalances black heights in RB trees. By extension, this paper projects three SA mathematical equations, namely, general symbolic arithmetic rule; partial symbolic arithmetic rule1; and partial symbolic arithmetic rule2. The removal of a DB node ultimately affects black heights in RB trees. To balance black heights using the SA equations, all the RB tree cases, namely, LR, RL, LL, and RR, were considered in this work; and the position of the nodes connected directly or indirectly to the DB node was also tested. In this study, to balance a RB tree, the issues considered w.r.t. the different cases of the RB tree were i) whether a DB node has an inner, outer, or both inner and outer black nephews; or ii) whether a DB node has an inner, outer or both inner and outer red nephews. The nephews r and x in this work are the children of the sibling s to a DB, and further up the tree, the parent p of a DB is their grandparent g. Thus, r and x have indirect relationships to a DB at the point of formation of the DB node. The novelty of the SA equations is in their effectiveness in the removal of DB that involves rotation of nodes as well as the recoloring of nodes along any simple path so as to balance black heights in a tree.
• Abstract（参考訳）: ダブルブラック(DB)ノードは、レッドブラック(RB)ツリーにはない。 そのため、DBノードが生成されると、それらはすぐに削除される。 他の連結ノードの回転と再色を引き起こすDBノードの除去は、RBツリーの教育と学習において大きな課題となる。 そこで本研究では,DBノードを除去する記号代数学(SA)法について,これまでの研究を拡張した。 Red + Black = Black; Black - Black = Red; Black + Black = DB; そして DB - Black = Black は DB ノードを削除し、RB ツリーの黒高さを再調整する。 拡張により, 一般記号算術規則, 部分記号算術規則1, 部分記号算術規則2の3つのSA式が提案される。 DBノードの削除は、最終的にRBツリーの黒い高さに影響を与える。 SA方程式を用いて黒高さのバランスをとるために、この研究では、RBツリーのすべてのケース、LR、RL、LL、RRが検討され、DBノードに直接または間接的に接続されたノードの位置も試験された。 本研究では, RB木のバランスをとるために, RB木の異なる事例について考察した。 一 DBノードが内側、外側、又は内側及び外側の黒の甥を有するか否か。 二 DBノードが内側、外側又は内側及び外側の赤色の甥を有するか。 この研究における甥 r と x は、兄弟 s から DB への子供であり、さらに木の上では、DB の親 p は彼らの祖父母 g である。 したがって、r と x は DB ノードの形成点で DB と間接的関係を持つ。 SA方程式の新規性は、樹高のバランスをとるため、ノードの回転と任意の単純な経路に沿ったノードの再色を含むDBの除去において有効である。

関連論文リスト

• Heterogeneous Graph Neural Network on Semantic Tree [11.810900066591861]
  HetTreeは、グラフ構造とヘテロジニアスの両方をスケーラブルで効果的な方法でモデル化する、新しいHGNNである。 セマンティックツリーを効果的にエンコードするために、HetTreeは、親子関係をエンコードするのに役立つメタパスを強調するために、新しいサブツリーアテンションメカニズムを使用している。 さまざまな実世界のデータセット上でのHetTreeの評価は、既存のすべてのベースラインをオープンベンチマークで上回っていることを示す。
  論文  参考訳（メタデータ） (2024-02-21T03:14:45Z)
• EntailE: Introducing Textual Entailment in Commonsense Knowledge Graph Completion [54.12709176438264]
  Commonsense knowledge graph(CSKG)は、名前付きエンティティ、短いフレーズ、イベントをノードとして表現するために自由形式のテキストを使用する。 現在の手法では意味的類似性を利用してグラフ密度を増大させるが、ノードとその関係のセマンティックな妥当性は未探索である。 そこで本研究では,CSKGノード間の暗黙的な包絡関係を見つけるために,テキストエンテーメントを導入し,同じ概念クラス内のサブグラフ接続ノードを効果的に密度化することを提案する。
  論文  参考訳（メタデータ） (2024-02-15T02:27:23Z)
• Probabilistic Tree-of-thought Reasoning for Answering Knowledge-intensive Complex Questions [93.40614719648386]
  大規模言語モデル(LLM)は、知識集約的な複雑な質問にチェーン・オブ・シント(CoT)推論で答えることができる。 最近の研究は、CoT推論を強化するための外部知識の回収に向けられている。 確率的ツリー・オブ・シント推論(ProbTree)という新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2023-11-23T12:52:37Z)
• Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with Scalability [76.62673276574668]
  バイナリバランスツリーRvNN(BBT-RvNNs)は、バランスの取れたバイナリツリー構造に従ってシーケンス合成を実行する。 BBT-RvNNはLong Range Arena (LRA)のようなロングシーケンスタスクにおいて効率的かつスケーラブルである リストOpsで成功するRvNN(例:ビームツリーRvNN)は、一般的にRNNよりも数倍高い。
  論文  参考訳（メタデータ） (2023-11-08T04:20:56Z)
• On the Two Sides of Redundancy in Graph Neural Networks [6.14580854336436]
  我々は近所の木に基づく新しい集約手法を開発した。 近傍木をコンパクトに表現し,それらをマージし,計算冗長性を生かした。 我々の手法は従来のメッセージパッシングニューラルネットワークよりも過度に理解されにくい。
  論文  参考訳（メタデータ） (2023-10-06T12:09:09Z)
• DeepTree: Modeling Trees with Situated Latents [8.372189962601073]
  そこで本研究では,木を手作業で定義するのではなく,分岐構造に対する発達規則を学習する手法を提案する。 我々は、その振る舞いが本質的な状態によって決定されるため、潜伏状態にあるディープニューラルモデル(deep Neural model)と呼ぶ。 本手法では,複雑なパラメータを定義することなく,多様な木形を生成することができる。
  論文  参考訳（メタデータ） (2023-05-09T03:33:14Z)
• RLET: A Reinforcement Learning Based Approach for Explainable QA with Entailment Trees [47.745218107037786]
  本稿では,強化学習に基づくEntailment Tree生成フレームワークであるRLETを提案する。 RLETは文の選択と推論生成モジュールによる単一ステップ推論を反復的に行う。 EntailmentBankデータセットの3つの設定の実験では、RLフレームワークを使用することの強みが示されている。
  論文  参考訳（メタデータ） (2022-10-31T06:45:05Z)
• Structure-Unified M-Tree Coding Solver for MathWord Problem [57.825176412485504]
  従来,数式表現の2次木構造を考慮に入れたモデルでは,性能が向上した。 本稿では、出力構造を統一するために、任意のM枝(M-tree)を持つ木を適用した構造統一M-Tree符号化(S-UMCr)を提案する。 広く使われているMAWPSとMath23Kデータセットの実験結果は、SUMC-rが複数の最先端モデルを上回るだけでなく、低リソース条件下でもはるかに優れた性能を発揮することを示した。
  論文  参考訳（メタデータ） (2022-10-22T12:20:36Z)
• A Neural Tangent Kernel Formula for Ensembles of Soft Trees with Arbitrary Architectures [5.634825161148483]
  ソフトツリーは、勾配法を用いて分割規則を更新する決定ツリーの活発に研究された変種である。 任意の木構造に対してソフトツリーアンサンブルによって誘導されるニューラルカーネルタンジェント(NTK)を定式化し解析する。
  論文  参考訳（メタデータ） (2022-05-25T16:49:29Z)
• Graph Tree Neural Networks [0.43012765978447565]
  グラフツリーニューラルネットワーク(GTNN)は、人間のニューラルネットワークの構造を分析することによって、既存のネットワークの問題を解決するように設計されている。 GTNNでは、情報ユニットはグラフの形式と関連付けられ、その後再び大きな情報の単位となり、他の情報ユニットと関係を持つ。
  論文  参考訳（メタデータ） (2021-10-31T07:58:00Z)
• Reasoning Graph Networks for Kinship Verification: from Star-shaped to Hierarchical [85.0376670244522]
  階層型推論グラフネットワークの学習による顔の親和性検証の問題点について検討する。 より強力で柔軟なキャパシティを利用するために,星型推論グラフネットワーク(S-RGN)を開発した。 また、より強力で柔軟なキャパシティを利用する階層型推論グラフネットワーク(H-RGN)も開発しています。
  論文  参考訳（メタデータ） (2021-09-06T03:16:56Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。