二分探索木を利用したソートの実装【Python】【Java】

二分探索木の特性を利用したソートアルゴリズムを実装してみます。

今回はノードクラスとドライバクラスを一括して書いていきます。

探索木クラス

コンストラクタ

class BST:
    def __init__(self, key, left = None, right = None) -> None:
        self.left  = left
        self.right = right
        self.key  = key
        pass

データの追加メソッド

def insert(self,data) -> None:
        if self.key < data:
            if self.right is None:
                self.right = Tree(data)
            else:
                   self.right.insert(data)
        elif self.key >= data:
            if self.left is None:
                self.left = Tree(data) 
            else:
                self.left.insert(data)

ターミナル出力用メソッド

def BST_out(self):
        if self.left:
            self.left.BST_out()
        print(self.key)
        if self.right:
            self.right.BST_out()

全域探索+最小値を見つけるメソッド

def a(self,m):
        if self.left is not None:
            m = min(self.left.key,m)
            self.left.a(m)
        if self.right is not None:
            m = min(self.right.key,m)
            self.right.a(m)
        return m

実行結果

root = BST(40)
for i in range(39,900):
    root.insert(i)
root.BST_out()
>>>
39
40
40
41
42
43
44
.
.
.
892
893
894
895
896
897
898
899

深さ優先探索アルゴリズム

再帰を利用して、深さ優先探索を行います。今回はソートに都合がよいので、Inorderという巡回経路を使用します。

def inorder(self,node) -> list[int]:
        if node is None:
            return []
        else:
            return self.inorder(node.left) + [node.key] + self.inorder(node.right)

二分探索木ソート

上記の深さ優先巡回アルゴリズムを使用して、入力配列をソートします。

def BST_sort(array:list[int]) -> list[int]:
    out_ = Tree(array[0])
    for i in array[1:]:
        out_.insert(i)
    return out_.inorder(out_)
BST_sort([5,4,3,3,4,1,4,1,99591348,1])
>>>
[1, 1, 1, 3, 3, 4, 4, 4, 5, 99591348]

Javaで実装(Comparable<T>)

ジェネリックタイプを使用できるようにComparableクラスを継承します。

クラス

public class BST <T extends Comparable<T>>{

    private  T key;
    private BST left = null;
    private BST right = null;

    public BST(){
    }

    public BST(T key){
        this.key = key;
    }
...

Insertメソッド

public void insert(T val){
        if (this.key.compareTo(val) < 0){
            if (this.right == null){
                this.right = new BST<T>(val);
            }else{
                this.right.insert(val);
            }
        }else{
            if (this.left == null){
                this.left = new BST<T>(val);
            }else{
                this.left.insert(val);
            }
        }
    }

深さ優先探索メソッド(Inorder)

ジェネリックタイプの配列を宣言できないので、Stringとして結果を取り出します。

public String inorder(BST root,String array){
            if (root == null){
                return array;
            }else{
               return this.inorder(root.left, array) + root.key +","+ this.inorder(root.right, array);
            }
    }

ターミナル出力メソッド

toStringをオーバーライド場合の再帰的な実装方法がわからなかったので、独自に定義します。

 public void BSTout(){
        if (this.left != null){
            this.left.BSTout();
        }
        System.out.println(this.key);
        if (this.right != null){
            this.right.BSTout();
        }
    }

ソートメソッド

public String BSTsort(T[] array){
        BST out = new BST(array[0]);
        for (int i = 0; i<array.length;i++){
            out.insert(array[i]);
        }
        return "[" + out.inorder(out, "").substring(0, array.length*2-1) + "]";
    }

実行結果

 public static void main(String[] args) {
        BST bst = new BST<>();
        String[] array = new String[26];
        for (int i = 0; i < 26; i++) {
            array[25-i] = "" + (char) (97+i);
        }

        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
        System.out.println(bst.BSTsort(array));
    }
>>>
 BST 
z
y
x
w
v
u
t
s
r
q
p
o
n
m
l
k
j
i
h
g
f
e
d
c
b
a
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]

計算量解析

１つの要素を追加する際にかかる時間計算量は$O(\lg n)$です。これが$n$個あるので、追加に必要な時間計算量は$n\lg n$となります。しかし、最悪の場合(木がただの線形リストになった場合）は$O(n^2)$かかることになるため、平衡二分探索木アルゴリズムを使用する必要があります。

また、探索木を格納するスペースが必要なので、空間計算量は$O(n)$となります。