Python上級

上級 Pythonで学ぶデータ構造｜練習問題編

 

導入

データ構造はプログラムの効率性や可読性に大きく影響を与えます。特に、実務で遭遇する問題に対して適切なデータ構造を選択することは、パフォーマンスの向上に直結します。本記事では、上級者向けに実際の業務シナリオを通じて、データ構造の選択とその実装方法を学びます。

教科書レベルの解説（データ構造）

重要な概念の整理

データ構造には多くの種類がありますが、ここでは特に「ハッシュテーブル」と「ツリー構造」に焦点を当てます。ハッシュテーブルは高速なデータ検索を可能にし、ツリー構造はデータの階層的な管理に役立ちます。現場では、これらのデータ構造を組み合わせて使用することが多く、例えば、ハッシュテーブルを用いてツリーのノードを効率的に管理するケースが見られます。

コード例（Python）


class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = TreeNode(key)
        else:
            self._insert_rec(self.root, key)

    def _insert_rec(self, node, key):
        if key < node.val:
            if node.left is None:
                node.left = TreeNode(key)
            else:
                self._insert_rec(node.left, key)
        else:
            if node.right is None:
                node.right = TreeNode(key)
            else:
                self._insert_rec(node.right, key)

    def search(self, key):
        return self._search_rec(self.root, key)

    def _search_rec(self, node, key):
        if node is None or node.val == key:
            return node
        if key < node.val:
            return self._search_rec(node.left, key)
        return self._search_rec(node.right, key)

コードの行ごとの解説

  1. class TreeNode: - ツリーのノードを表すクラスを定義します。
  2. def __init__(self, key): - ノードの初期化メソッド。左と右の子ノードをNoneに設定します。
  3. class BinaryTree: - バイナリツリーを管理するクラスを定義します。
  4. def insert(self, key): - ツリーに新しいキーを挿入するメソッドです。
  5. def _insert_rec(self, node, key): - 再帰的にノードを挿入するプライベートメソッドです。
  6. def search(self, key): - ツリー内でキーを検索するメソッドです。
  7. def _search_rec(self, node, key): - 再帰的にノードを検索するプライベートメソッドです。

練習問題編

以下に3つの練習問題を用意しました。各問題に対する模範解答も併せて記載します。

問題1

バイナリツリーに整数を挿入し、そのツリーの深さを計算するメソッドを実装してください。


def max_depth(node):
    if node is None:
        return 0
    else:
        return 1 + max(max_depth(node.left), max_depth(node.right))

問題2

バイナリツリーを中間順に走査し、ノードの値をリストとして返すメソッドを実装してください。


def inorder_traversal(node):
    return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right) if node else []

問題3

与えられたキーがツリーに存在するかどうかを確認するメソッドを実装してください。


def exists_in_tree(tree, key):
    return tree.search(key) is not None

まとめ

  • データ構造の選択は業務上の効率性に直結します。
  • ハッシュテーブルとツリー構造を組み合わせることで、より複雑なデータ管理が可能です。
  • 実際の業務で直面する問題を解決するためには、適切なデータ構造の理解が不可欠です。
RELATED POST