-
Notifications
You must be signed in to change notification settings - Fork 4
/
481.txt
91 lines (63 loc) · 4.2 KB
/
481.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
[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>
]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>