Edit

Page

Page title:

Page body:

[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]] 版) <https://dom.spec.whatwg.org/#concept-tree-root>
- [24] [CITE@en[DOM Standard]] ([TIME[2017-09-15 01:44:22 +09:00]]) <https://dom.spec.whatwg.org/#dom-node-getrootnode>
]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]] 版))
<http://www.w3.org/TR/xpath-datamodel-3/#dt-root-node>

[2] [CITE@en[Add Node.prototype.rootNode · whatwg/dom@0316b62]]
([TIME[2016-03-08 18:14:44 +09:00]] 版)
<https://github.com/whatwg/dom/commit/0316b621cfe8a7aa4ad50a2ec7d10dba902ddccb>

[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]] 版)
<https://github.com/w3c/webcomponents/commit/959d8026056976b24e5eccc55eb3190e7719cf8d>

[9] [CITE@en[Editorial: add sections on document and shadow trees · whatwg/dom@018440e]] ([TIME[2016-03-20 18:28:50 +09:00]] 版) <https://github.com/whatwg/dom/commit/018440e918b59633eb0a6b9033528f612f84aa49>

[16] [CITE@en[Remove Node.prototype.rootNode]]
( ([[annevk]]著, [TIME[2016-06-07 17:53:11 +09:00]]))
<https://github.com/whatwg/dom/commit/42a45eb0d1af13e510620b6b29696997f0c7aa3d>

[17] [CITE@en[Add Node.prototype.getRootNode()]]
( ([[annevk]]著, [TIME[2016-06-09 16:53:30 +09:00]]))
<https://github.com/whatwg/dom/commit/579ef079ded65daa981cac974648621790839072>

[21] [CITE@en[XQuery and XPath Data Model 3.1]]
([TIME[2017-03-20 07:26:25 +09:00]])
<https://www.w3.org/TR/2017/REC-xpath-datamodel-31-20170321/#dt-root-node>

[22] [CITE@en[Editorial: getRootNode() is a method]]
([[annevk]]著, [TIME[2017-07-24 16:22:50 +09:00]])
<https://github.com/whatwg/dom/commit/b8d9f4e4a319d3050df0e9242a8d3d2733ba67fa>

[23] [CITE@en["The getRootNode(options) attribute’s getter" · Issue #481 · whatwg/dom]]
([TIME[2017-07-25 11:28:35 +09:00]])
<https://github.com/whatwg/dom/issues/481>

Historical Legal Sensitive Parent: [Help / License]

Edit

Page

Page name(s)