[1] [[データ構造]]である[[木]]の中で、[[植物]]の[[木]]の[[根]]にあたる部分の[[節点]]を、 [DFN[[RUBY[根節点] [ねせってん] @en[root node]]]]、 あるいは単に[DFN[[RUBY[根] [ね] @en[root]]]]といいます。 [4] [[木]]のほとんどの[[節点]]は[[親節点]]を持ちますが、 唯一[[根]]だけは[[親節点]]がありません。 [5] 「[[根節点]]」という時、データモデルによっては特定の節点の種類を表しますが、 別のデータモデルでは木構造中の位置を表します。具体的には、 [[XPath 1.0データ・モデル]]では「[[根節点]]」とは [[DOM]] の[[文書節点]]に相当する[[節点]]の種類ですが、 [[XDM]] では「[[根節点]]」とは種類に関わらず[[木構造]]の[[根]]に位置する[[節点]]のことです。 * 仕様書 [REFS[ - [10] [CITE@en-US[DOM Standard]] ([TIME[2013-09-23 20:54:24 +09:00]] 版) - [24] [CITE@en[DOM Standard]] ([TIME[2017-09-15 01:44:22 +09:00]]) ]REFS] * 定義 [11] [[オブジェクト]]の[DFN[[F[[RUBYB[[[根]]]@en[root]]]]]]は、 その[F[親]]が [[null]] ならそれ自体、 それ以外ならその[F[親]]の[F[根]]です [SRC[>>10]]。 ;; [12] つまり、[F[親]]をたどってそれ以上たどれなくなったら、それが[[根]]です。 [6] [[木]]の[DFN[[F[[RUBYB[[[根]]]@en[root]]]]]]は、 それに[[属する][participate]][[オブジェクト]]のうち、 その[F[親]]が [[null]] であるものです [SRC[>>10]]。 ;; [13] そのような[[オブジェクト]]は、[[木]]ごとにちょうど1つだけ存在します。 ;; [14] [[木]]の[F[根]]は、[[木]]に[[属する][participate]]任意の[[オブジェクト]]の[F[根]]と常に一致します。 * 根の取得 [18] ある[[節点]]の[F[根]]は、その[[節点]]の[F[親]]をたどっていくことで取得できます。 その[[計算量]]は深さ ([[根]]から当該[[節点]]までの[[枝]]の数) ですから、 おおよそ平均的には [CODE(math)[[[O][O()]]([[log]]([VAR[n]]))]] (最悪 [CODE(math)[[[O][O()]]([VAR[n]])]]) となります。 [19] [[木]]を保持する[[データ構造]]や、速い探索のための最適化の方法次第で、 より高速に取得できることがあります。 [EG[ [20] 例えば多くの [[DOM]] の実装は、少なくても主たる[[文書木]]については、 [CODE[[[O][O()]](1)]] で[[節点]]の[F[根]]にアクセスできるように参照を保持しているようです。 ]EG] * 根要素 [7] 「[[根要素]]」は[[要素]]のみを考えた時[[根]]にあたるものです。必ずしも[[根節点]]と同一ではありません。 ;; [[根要素]]参照。 * 影を含む根 [15] [[影木]]も含めた全体の[[根]]を[[影を含む根]]といいます。 ;; [[影を含む根]]参照。 * 歴史 [8] [CITE@en[XQuery and XPath Data Model 3.0]] ( ([TIME[2014-04-08 07:00:06 +09:00]] 版)) [2] [CITE@en[Add Node.prototype.rootNode · whatwg/dom@0316b62]] ([TIME[2016-03-08 18:14:44 +09:00]] 版) [3] [CITE@en[''''''[''''''Issue #80'''''']'''''' Remove Node.treeRoot because it was renamed and was upstr… · w3c/webcomponents@959d802]] ([TIME[2016-03-08 18:26:27 +09:00]] 版) [9] [CITE@en[Editorial: add sections on document and shadow trees · whatwg/dom@018440e]] ([TIME[2016-03-20 18:28:50 +09:00]] 版) [16] [CITE@en[Remove Node.prototype.rootNode]] ( ([[annevk]]著, [TIME[2016-06-07 17:53:11 +09:00]])) [17] [CITE@en[Add Node.prototype.getRootNode()]] ( ([[annevk]]著, [TIME[2016-06-09 16:53:30 +09:00]])) [21] [CITE@en[XQuery and XPath Data Model 3.1]] ([TIME[2017-03-20 07:26:25 +09:00]]) [22] [CITE@en[Editorial: getRootNode() is a method]] ([[annevk]]著, [TIME[2017-07-24 16:22:50 +09:00]]) [23] [CITE@en["The getRootNode(options) attribute’s getter" · Issue #481 · whatwg/dom]] ([TIME[2017-07-25 11:28:35 +09:00]])