ツリーソート

1. ツリーソートアルゴリズム
2. ツリーソートの例
3. ツリーソートアルゴリズムの実装
4. ツリーソートアルゴリズムの複雑さ

ツリーソートはオンラインソートアルゴリズムです。これは、要素を格納するためにバイナリ検索木のデータ構造を使用します。要素は、バイナリ検索木を順番にトラバーサルすることで、ソートされた順番で検索することができます。これはオンラインソートアルゴリズムなので、挿入された要素は常にソートされた順序で維持されます。

ツリーソートアルゴリズム

n 個の要素を含むソートされていない配列 A[] があるとしましょう。

TreeSort()

Insert()

Inorder()

ツリーソートの例

配列 (5, 3, 4, 2, 1, 6) があるとしましょう。これを挿入ソートアルゴリズムを用いてソートします。

まず、ルートノード 5 を作成して BST を初期化します。

3 は 5 より小さいので、5 の左に挿入されています。

4 は 5 より小さいが 3 より大きいので、3 の右に挿入され、4 の左に挿入されています。

2 は現在のツリーの中で最も小さい要素なので、一番左の位置に挿入されています。

1 は現在のツリーの中で最も小さい要素なので、左端に挿入されています。

6 は現在のツリーの中で最大の要素なので、右端の位置に挿入されています。

BST が構築された後、最終的にソートされた配列 (1, 2, 3, 4, 5, 6) を得るために木を順に探索します。

ツリーソートアルゴリズムの実装

#include <bits/stdc++.h>

using namespace std;

class Node {
 public:
  int key;
  Node *left, *right;
};

Node *newNode(int item) {
  Node *temp = new Node;
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

void inorder(Node *root, int arr[], int &i) {
  if (root != NULL) {
    inorder(root->left, arr, i);
    arr[i++] = root->key;
    inorder(root->right, arr, i);
  }
}

Node *insertintoBST(Node *node, int key) {
  if (node == NULL) return newNode(key);
  if (key < node->key)
    node->left = insertintoBST(node->left, key);
  else if (key > node->key)
    node->right = insertintoBST(node->right, key);
  return node;
}

void treeSort(int arr[], int n) {
  Node *root = NULL;
  root = insertintoBST(root, arr[0]);
  for (int i = 1; i < n; i++) root = insertintoBST(root, arr[i]);
  int i = 0;
  inorder(root, arr, i);
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  treeSort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

ツリーソートアルゴリズムの複雑さ

時間計算量

• 平均のケース

平均的なケースでは、BST に n ノードを挿入する時間の複雑さは O(nlogn) のオーダーです。これは、形成される BST がバランスのとれた BST である場合に発生します。したがって、時間の複雑さは [Big Theta]：O(nlogn) のオーダーです。

• 最悪のケース

最悪の場合は、配列がソートされ、最大高さ O(n) の不均衡な 2 値探索木が形成されます。高さが logn の通常の BST の場合の探索時間は O(logn) であるのに対し、探索には O(n) 時間、挿入には O(n²) が必要です。最悪の場合の時間的複雑さは [Big O]：O(n²)です。

これは AVL 木や赤黒木などのセルフバランス型のデータ構造を用いれば、O(nlogn) に削減できます。

• 最良のケース

ベストケースは形成された二値探索木が均衡している場合です。最良の時間複雑度は [Big Omega]：O(nlogn) です。これは平均ケースの時間複雑度と同じです。

空間計算量

このアルゴリズムの空間複雑度は O(n) です。