平衡二分探索木 - Wikipedia
平衡二分探索木（へいこうにぶんたんさくぎ、英: self-balancing binary search tree）とは、計算機科学において二分探索木のうち木の高さ（根からの階層の数）を自動的にできるだけ小さく維持しようとするもの（平衡木）である。平衡二分探索木は連想配列や集合その他の抽象データ型を実装する最も効率のよいデータ構造の1つである。 概要[編集] 二分探索木上の大半の操作にかかるコストは木の高さに比例するので木の高さは低く保つのが望ましい。通常の二分探索木の主要な欠点は、キーが辞書順に挿入されるような普通の状況で木の高さが大きくなってしまうということである。結果として連結リスト同様のデータ構造になってしまい、全ての操作が高くつく結果となる。もしあらかじめ全てのデータが分かっているならば、値をランダムに追加することで木の高さを平均的に小さく保つことができるが、そのような贅沢はいつ
二分木 - Wikipedia
簡単な二分木。大きさ9、深さ3、根は値2を持つ 二分木（にぶんぎ）は、データ構造の1つである。二進木（にしんぎ）やバイナリツリー（英: binary tree）とも呼ばれ、根付き木構造の中で、全てのノード（節点 node）が持つ子の数が高々2であるものをいう。典型的には2つの子はそれぞれ「左」「右」と呼ばれる。 たとえば、二分探索や二分ヒープを実装するために使われる。 以後、括弧の中は英語表記。 用語[編集] 親から子へ有向線分（辺、エッジ edge）が引かれる。子を持たないノードを葉（リーフ leaf）ないし外部ノード (external node) と呼ぶ。葉でないノードを内部ノード (internal node) と呼ぶ。あるノードの「深さ」(depth) はルート（root 「根」にあたるノード）からそのノードまでにたどる経路（パス path）の長さ（経路の種類ではなく、ノード-ノ
Binary tree - Wikipedia
A labeled binary tree of size 9 (the number of nodes in the tree) and height 3 (the height of a tree defined as the number of edges or links from the top-most or root node to the farthest leaf node), with a root node whose value is 1. The above tree is unbalanced and not sorted. In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as
二分探索木 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "二分探索木" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2023年3月） 二分探索木 二分探索木（にぶんたんさくぎ、英: binary search tree）は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。 構造[編集] 構造は二分木と同じだが、「左の子孫の値 ≤ 親 ≤ 右の子孫の値」という制約を持つ。左の子孫の値と右の子孫の値の両方に等号をつけているが、実際にはどちらかに統一しておく必要がある。 平衡（左右のバランスがとれてい
Binary search tree - Wikipedia
Fig. 1: A binary search tree of size 9 and depth 3, with 8 at the root. The leaves are not drawn. In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. The time complexit
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
