python classの使い方

Question

前提・実現したいこと

2分探索木をpythonで実装しようと考えています．
とりあえず，ネットに落ちていたものをベースにしようと考えていしたが，

プログラム内self.insert()　（Solutionクラスのinsert関数内）とroot.left（Solutionクラスのinsert関数内）が何を表しているのかがわかりません．

selfがつくのはインスタンス変数などを呼び出すときに使用する時なのでは
またroot.leftは，rootをインスタンス化しなければつかえないのでは

発生している問題・エラーメッセージ

エラーは出ていません

該当のソースコード

class Node:
    def __init__(self,data):
        self.right=self.left=None
        self.data = data

class Solution:
    def insert(self,root,data):
        if root==None:
            return Node(data)
        else:
            if data<=root.data:
                cur=self.insert(root.left,data)
                root.left=cur
            else:
                cur=self.insert(root.right,data)
                root.right=cur
        return root
    
    def getHeight(self,root):
        if root == None:
            return -1
        return 1 + max(self.getHeight(root.left), self.getHeight(root.right))

T=int(input())
myTree=Solution()
root=None
for i in range(T):
    data=int(input())
    root=myTree.insert(root,data)
height=myTree.getHeight(root)
print(height)  

試したこと

ここに問題に対して試したことを記載してください。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Answer 1

selfがつくのはインスタンス変数などを呼び出すときに使用する時なのでは

そんなことはありません。
スタティックメソッドやプロパティは、インスタンス化（初期化）せずとも、そのまま使用できます。

ただし、今回の構文は初期化を行っています。
故に、selfはインスタンスのアクセサとして機能しています。

またroot.leftは，rootをインスタンス化しなければつかえないのでは

上記記載のように、今回の構文はインスタンス化を行っています。

プログラム内self.insert()　（Solutionクラスのinsert関数内）とroot.left（Solutionクラスのinsert関数内）が何を表しているのかがわかりません．

上記を踏まえて、下記で何をしているかのコメントを記述してみました。

class Node:
    def __init__(self,data):
        # ただ単に、Nodeクラスの初期化
        self.right=self.left=None
        self.data = data

class Solution:
    def insert(self,root,data):
        if root==None:
            # rootがNoneだった場合は、Nodeクラスを初期化して、返す
            # 最初は、rootにNoneを代入して実行しているため、一発目はここを通る
            return Node(data)
        else:
            # rootに既に値が入っているため、様々処理を行う
            if data<=root.data:
                # 同クラスの同メソッドを改めて実行して再計算させている。
                # これを"再帰的処理"と言い、何回計算させるかわからない時や、深く処理を潜らせなければならない時に用いる処理法
                cur=self.insert(root.left,data)
                root.left=cur
            else:
                # 上記と同様に、再帰的処理を行っている
                cur=self.insert(root.right,data)
                root.right=cur
        # 処理を行ったNodeインスタンスを返す
        return root

    def getHeight(self,root):
        # rootの情報を使って、高さを返している
        if root == None:
            return -1
        return 1 + max(self.getHeight(root.left), self.getHeight(root.right))

# inputの実行値を整数に変換しTに格納
T=int(input())

# Solutionクラスを初期化し、myTreeに格納
myTree=Solution()

# rootにNoneを格納（最初は値がないことを示したいと思われる）
root=None

# Tの回数だけfor処理を実行
for i in range(T):
    # dataに、inputの実行値を整数に変換し、格納
    data=int(input())

    # rootに、myTree（Solutionクラス）のinsertメソッドの返却値を代入
    # insertメソッドは、引数がNoneだった場合は、Nodeクラスを初期化したインスタンスを返し、値が入っていれば、様々処理をした上で、Nodeのインスタンスを返す
    root=myTree.insert(root,data)

# root（Nodeのインスタンス）を使って、高さを取得している
height=myTree.getHeight(root)

# 上記を表示
print(height) 

以上です。
参考になれば幸いです。

どこをどういう順番で通るか、を意識して見ていくといいかと。

Comments

[LouiS0616]

重箱の隅で恐縮ですが、『再起』は『再帰』の誤字ですね。
https://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0

[miyabi_pudding]

間違った・・・。
ご指摘ありがとうございます。

[NR4200]

丁寧なご回答ありがとうございます．

root.leftのところで質問なのですが，
class内でないところで，
root=myTree.insert(root,data)
と記述することによって，
rootがインスタンス化され，classないで，root.leftが使えるという認識でいいのでしょうか？

[miyabi_pudding]

うーん、結果的には間違っていないのですが、
正確には、
insertメソッドが、
Nodeのインスタンスを返すようになっており、
その値がrootに代入されているだけです。
return文をしっかり学習してください。

それを、再帰実行で、再度引数に入れて実行することで、
rootの値を引き継いで再計算しています。

ですが、外側のrootと、insertメソッド内のrootは同値ですが、
まったく別物という認識は忘れずに。
つまり、厳密に言えば、

> rootがインスタンス化され

という認識は間違っています。
あくまで、外側のrootには、insertメソッドから返された値が代入されているだけです。

[NR4200]

何度も質問して申し訳ございません。

一回目のinsertメソッドでのreturnで rootという名前の<Node>classのインスタンス化をつくる．
二回目以降で，インスタンス化した<Node>classのrootのインスタンス変数を変更している？

もし上記の考えがあっているならば，
二回目以降のmyTree.insert(root,data)の引数rootは，<Node>classのインスタンス化したものが引数として渡されている．

[miyabi_pudding]

その解釈であっていると思います。

[NR4200]

丁寧な解説，ありがとうございました．