トリプルルーティングの実装

5856 ワード
Trie テキストリンク
この記事は、gogaegaebal、コーディングジミーのブログを参考にして書かれています.写真(Photo)をクリックして、各写真のソースに移動します.

三輪車


  • 文字列はツリー形式で行われ、バイナリ検索ツリーの原理と似ているため、文字列をすばやく検索できる資料構造である.
  • 文字を基準として、ツリーのサブアイテムを下に検索します.
  • 所要時間はO(m)である.mは文字列長
  • は自動的に完成し、検索語推薦機能によく使われる.

    • コード実装


    ノード

    class Node(object):
    def __init__(self, key, data=None):
        self.key=key        # 문자
        self.data=data      # 단말노드인 경우 문자저장
        self.children={}    # 자식노드

    三輪車

    class Trie:
    # 트라이 초기화
    def __init__(self):
        self.head=Node(None)

    # 문자열 삽입
    def insert(self, string):
        current_node=self.head

        for char in string:
            if char not in current_node.children:
                current_node.children[char] = Node(char)
            current_node = current_node.children[char]
        current_node.data=string

    # 문자열 검색
    def search(self, string):
        current_node=self.head

        for char in string:
            if char in current_node.children:
                current_node = current_node.children[char]
            else:
                return False

        # 마지막까지 탐색했을때 그 단어가 단말노드면
        if current_node.data:
            return True
        else:
            return False
    推奨事項
    BOJ 5052電話リスト
    Linux/proc/meminfoファイルの詳細
    BOJ 1918-接尾辞式