|
(n) binary tree =========================== ・ 二 ： [に] 1. (num) two ・ 二分木 ： [にぶんぎ] (n) binary tree ・ 分 ： [ぶん, ふん] 1. (n,n-suf,pref) (1) part 2. segment 3. share 4. ration 5. (2) rate 6. (3) degree 7. one's lot 8. one's status 9. relation 10. duty 1 1. kind 12. lot 13. (4) in proportion to 14. just as much as 1 ・ 分木 ： [ぶんぎ] (n) -ary tree ・ 木 ： [き] 【名詞】 1. tree 2. wood 3. timber
計算機科学でいう二分木（; 二進木、バイナリツリー）は、データ構造の1つである。根付き木構造の中で、あるノード（節点 node）が持つ子の数が高々2であるものをいう。典型的には2つの子はそれぞれ「左」「右」と呼ばれる。 たとえば、二分探索や二分ヒープを実装するために使われる。 以後、括弧の中は英語表記。 たとえば、二分探索や二分ヒープを実装するために使われる。 以後、括弧の中は英語表記。 == 用語 == 親から子へ有向線分（辺、エッジ edge）が引かれる。子を持たないノードを葉（リーフ leaf）ないし外部ノード (external node) と呼ぶ。葉でないノードを内部ノード (internal node) と呼ぶ。あるノードの「深さ」(depth) はルート（root 「根」にあたるノード）からそのノードまでにたどる経路（パス path）の長さ（経路の種類ではなく、ノード-ノードを1と数えた数）である。特定の「深さ」のノードを総称して木の中での「レベル」(level) と称することがある。あるノードの「高さ」 (height) はそのノードから最も遠い葉までの経路の長さである。同じ親を持つノード同志を兄弟 (siblings) であると呼ぶ。ノードpからノードqまでの経路がある場合、pはqの「先祖」(ancestor)、qはpの「子孫」(descendant) である。ノードの「大きさ」(size) は（自分自身を含んだ）そのノードの子孫の数である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「二分木」の詳細全文を読む スポンサード リンク
|