ree(1)-ツリーコンセプト、バイナリツリー、バイナリ検索ツリー
4231 ワード
0.樹用語整理
ツリー
回数
1.バイナリツリー-バイナリツリー
1.1. What is binary tree?
# 이진트리 기본코드
class BinaryTreeNode:
def __init__(self, value):
self.left = None #왼쪽 서브노드
self.value = value
self.right = None #오른쪽 서브노드1.2. バイナリツリータイプ
1) Binary Search Tree(BST)
（画像ソース）
すべての値はノードのサイズによって区別されます.
詳細は以下の1.3です.バイナリ検索ツリー(BST)-バイナリ検索ツリーを参照してください.
2) Balance
バランスツリーとアンバランスツリーがあり、ここでの「バランスが正しい」とは、左右のノードの数が完全に同じである必要はありません.
右側(アンバランス)ツリーのように、深刻なアンバランス状態でなければ、バランスツリーと呼ぶことができます.
3) Complete Binary Tree
ノードのバイナリツリーをツリーレベルで左側から塗りつぶします.
4) Full Binary Tree
ノードがChildを持っている場合、2つのChildを持っているか、いっそ1つも持っていないバイナリツリーを持っている.
すなわち,完全な二叉木にはChildの親ノードが1つしか存在しない.
5) Perfect Binary Tree
すべてのノードには2つのChildがあり,正確なピラミッド形状のバイナリツリーがある.
レベルの個数をnnnと呼ぶと、Perfectツリーの総ノード数=2 n–12^n-12 n–1となる.
上の図に示すように、n=3 n=3 n=3(合計3レベル)、総ノード数=23の1=72^3-1=723の1=7である.
1.3. バイナリ検索ツリー(BST)-バイナリ検索ツリー
バイナリ検索ツリーは、ノードを正しく位置合わせする必要がある特定のタイプのバイナリツリーです.
バイナリ検索ツリーは、値のサイズ条件に基づいてノードに値を割り当てる必要があります.
値サイズ条件
値サイズの条件は、次のノードの値サイズの順序に従います.
오른쪽 서브노드의 값(right child) > 루트(부모)노드의 값(root node) > 왼쪽 서브노드의 값(left child)さらに、バイナリ検索ツリーは、単純なバイナリツリーよりもノードの参照速度が速くなります.これは、値のサイズ条件を満たすためにノードに値を入れるためです.
バイナリ検索ツリー検索プロシージャ
また,探索速度は通常のバイナリツリーよりも速いため,ノードの挿入が容易である.
（画像ソース）
上記のバイナリ検索ツリーで43値のノードを検索します.
1)43と50(ルートノード値)を比較する
2)左ノードに移動(43<50)
3)43と25を比較する
4)43>25、右側ノードに移動
5)43と40を比較する
6)43>40、右側ノードに移動
7)43個のノードの検索に成功
Created on Nov 25, 2021
Reference
この問題について(ree(1)-ツリーコンセプト、バイナリツリー、バイナリ検索ツリー), 我々は、より多くの情報をここで見つけました https://velog.io/@citizenyves/Tree1-트리-자료구조-개념テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol