データ構造の二分木 (例)

二分木とは何ですか？

バイナリーという言葉はXNUMXという意味です。ツリーデータ構造「Binary Tree」において、各ノードが最大 XNUMX つの子ノード (左右のノード) を持つことができるツリーを意味します。単純な二分木です。

ただし、最も頻繁に使用され、さまざまな使用例がある別のバイナリツリーがあります。これはバイナリ検索ツリー (BST) と呼ばれます。このツリーを使用すると、検索アルゴリズムを大幅に高速化でき、正確には log(n) の時間計算量になります。データ構造では、n はバイナリツリーのノードの数を意味します。

二分木と二分探索木の違いは何ですか?

BST と通常の二分木の違いは、BST の左側のノードがルートノードよりも小さい値を持ち、右側のノードがルートノードよりも大きい値を持つことです。したがって、左側のサブツリーには常にルートより小さい値が含まれ、右側のサブツリーには常にルートより大きい値が含まれます。

二分探索木の例

二分探索木の概念を説明するために次の例を見てみましょう。

ここでは、すべてのノードが指定された規律に従うことができます。二分探索木の最大ノード数には公式があります。上記のツリーを観察すると、すべてのリーフノードを除いて、各ノードに 4 つの子があることがわかります。そして、指定された二分木の高さ(h)はXNUMXです。式は次のとおりです。 2^h - 1。したがって、15 になります。

上記の画像は完全なバイナリツリーまたはバランスバイナリツリーではなく、完全バイナリツリーまたはバランスバイナリツリーと呼ばれます。 AVL (別のタイプのバイナリツリー) と呼ばれる別のデータ構造があります。これは、バイナリツリーの高さを最適化し、図 3 のように BST の検索を高速化します。

上記のバイナリツリーの順序どおりのトラバーサルを計算してみてください。非減少のソートされた配列が生成され、トラバーサルアルゴリズムはバイナリツリーと同じになることがわかります。

二分木の種類

ここでは、バイナリツリーの重要なタイプをいくつか示します。

完全なバイナリツリー: このバイナリツリーでは、各ノードが 0 または 2 つの子ノードを持つことができます。このタイプのバイナリツリーでは、子ノードが 2 つだけ許可されません。したがって、リーフノードを除くすべてのノードには XNUMX つの子が存在します。

完全なバイナリツリー: 各ノードには 0 個または 2 個のノードを含めることができます。完全なバイナリツリーのように見えますが、すべてのリーフ要素は左側のサブツリーに偏っていますが、完全なバイナリツリーではノードが右側または左側のサブツリーに存在する可能性があります。

完璧な二分木: すべてのノードには 0 個または 2 個のノードが必要で、すべてのリーフノードは同じレベルまたは高さである必要があります。完全なバイナリツリー構造の上記の例は、ノード 6 とノード 1,2,3、XNUMX、XNUMX が同じ高さではないため、完全なバイナリツリーではありません。しかし、完全なバイナリツリーの例は、完全なバイナリツリーです。

縮退したバイナリツリー: 各ノードには 1 つの子しか存在できません。検索、挿入、削除などのすべての操作には O(N) の時間がかかります。

バランスの取れた二分木: この二分木では、左右のサブツリーの高さの差は最大でも 1 です。そのため、ノードを追加または削除するときに、ツリーの高さのバランスを再度調整する必要があります。このタイプの自己バランス型二分木は、 AVLツリー.

BST には 3 つの基本的な操作があります。これらについては以下で詳しく説明します。

C言語での二分木の実装と C++

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Node
{
   int value;
   struct Node *left, *right;
}
struct Node *getEmptynode(int val)
{
   struct Node *tempNode = (struct Node *)malloc(sizeof(struct Node));
   tempNode->value = val;
   tempNode->left = NULL;
   tempNode->right = NULL;
   return tempNode;
}
struct Node *successor(struct Node *node)
{
    struct Node *present = node;
// going to the left most node
    while (present != NULL && present->left != NULL)
    {
       present = present->left;
    }
     return present;
 }
struct Node *insert(struct Node *node, int value)
{
   if (node == NULL)
   {
      return getEmptynode(value);
   }
   if (value < node->value)
   {
      node->left = insert(node->left, value);
   }
   else
   {
      node->right = insert(node->right, value);
   }
      return node;
}
int searchInBST(struct Node *node, int value)
{
   struct Node *current = node;
   while (current->value != value)
    {
    if (current->value > value)
      {
      current = current->left;
      }
    else
     {
     current = current->right;
     }
   if (current == NULL)
     {
    return 0;
     }
   }
return 1;
}
void inorder(struct Node *root)
{
 if (root != NULL)
  {
   inorder(root->left);
   cout << root->value << " ";
   inorder(root->right);
  }
}
struct Node *deleteNode(struct Node *node, int value)
{
 if (node == NULL)
  {
   return node;
  }
 if (value < node->value)
  {
   node->left = deleteNode(node->left, value);
  }
else if (value > node->value)
 {
   node->right = deleteNode(node->right, value);
 }
else
{
if (node->left == NULL)
 {
 struct Node *temp = node->right;
 free(node);
 return temp;
 }
 else if (node->right == NULL)
 {
 struct Node *temp = node->left;
 free(node);
 return temp;
  }
 struct Node *temp = successor(node->right);
 node->value = temp->value;
 node->right = deleteNode(node->right, temp->value);
}
return node;
}
int main()
 {
  struct Node *root = NULL;
  root = insert(root, 8);
  root = insert(root, 4);
  root = insert(root, 12);
  root = insert(root, 2);
  root = insert(root, 6);
  root = insert(root, 10);
  root = insert(root, 14);
  root = insert(root, 1);
  root = insert(root, 3);
  root = insert(root, 5);
  root = insert(root, 7);
  root = insert(root, 9);
  root = insert(root, 11);
  root = insert(root, 13);
  root = insert(root, 15);

 cout << "InOrder Traversal after inserting all nodes: " << endl;
 inorder(root);
 root = insert(root, -10);
 cout << "\nInOrder Traversal after inserting -10 : " << endl;
 inorder(root);
 cout << "\nSearching -5 in the BST: " << searchInBST(root, -5) << endl;
 cout << "Searching -10 in the BST: " << searchInBST(root, -10) << endl;
 root = deleteNode(root,8);
 cout<<"After deleting node 8, inorder traversal: "<<endl;
 inorder(root);
 root = deleteNode(root,-10);
 cout<<"\nAfter deleting node -10, inorder traversal: "<<endl;
 inorder(root);
}

出力：

InOrder Traversal after inserting all nodes:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

InOrder Traversal after inserting -10 :
10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Searching -5 in the BST: 0
Searching -10 in the BST: 1

After deleting node 8, inorder traversal:
-10 1 2 3 4 5 6 7 9 10 11 12 13 14 15

After deleting node -10, inorder traversal:
1 2 3 4 5 6 7 9 10 11 12 13 14 15

バイナリツリーの実装 Python

class Node:
def __init__(self,value):
      self.left = None
      self.right = None
      self.value = value
def insert(root,value):
      if root == None:
          return Node(value)
      if value< root.value:
          root.left = insert(root.left,value)
      else:
          root.right = insert(root.right,value)
          return root
  def searchInBST(root,value):
      current = root
  while current.value != value:
  if current.value > value:
      current = current.left
  else:
      current = current.right
  if current == None:
      return "Not found"
      return "Found"
def inorder(root):
    if root != None:
      inorder(root.left)
      print(root.value,end=" ")
      inorder(root.right)
def successor(root):
    present = root
    while present != None and present.left != None:
    present = present.left
      return present
def deleteNode(root,value):
    if root == None:
      return root
    if value < root.value:
        root.left = deleteNode(root.left, value)
    elif value>root.value:
        root.right = deleteNode(root.right, value)
    else:
    if root.left == None:
        temp = root.right
        root = None
        return temp
    elif root.right == None:
        temp = root.left
        root = None
        return temp
        temp = successor(root.right)
        root.value = temp.value
        root.right = deleteNode(root.right, temp.value)
        return root
        root = Node(8)
        root = insert(root, 4)
        root = insert(root, 12)
        root = insert(root, 2)
        root = insert(root, 6)
        root = insert(root, 10)
        root = insert(root, 14)
        root = insert(root, 1)
        root = insert(root, 3)
        root = insert(root, 5)
        root = insert(root, 7)
        root = insert(root, 9)
        root = insert(root, 11)
        root = insert(root, 13)
        root = insert(root, 15)
  print("InOrder Traversal after inserting all nodes: ")
  inorder(root)
  root = insert(root, -10)
  print("\nInOrder Traversal after inserting -10 : ")
  inorder(root)
  print("\nSearching -5 in the BST: ",searchInBST(root, -5))
  print("Searching -5 in the BST: ",searchInBST(root, -10))
  root = deleteNode(root,8)
  print("After deleting node 8, inorder traversal:")
  inorder(root)
  root = deleteNode(root,-10)
  print("\nAfter deleting node -10, inorder traversal:")
  inorder(root)

出力：

InOrder Traversal after inserting all nodes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

InOrder Traversal after inserting -10 : -10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

Searching -5 in the BST: Not found 

Searching -5 in the BST: Found After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 

After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15

二分木の応用

Binary Tree の一般的なアプリケーションをいくつか示します。

ノードデータをソート順に整理する
プログラミング言語ライブラリのマップおよびセットノードオブジェクトで使用されます。
データ構造内の要素の検索

» 次のチュートリアルについて学ぶ組み合わせアルゴリズム

よろしければ：