完璧主義者脱却への道のり！ 2025/02/24

はじめに

完璧主義者脱却ための日記&学習記録，10日目です！
今日もゆる～く書いていきます．

にっき

今日は何もありませんでした！しいて言うならばちょっと悲しくてどうしようもできないことを親に言われてちょっとショックだったということくらいです．（これに関しては誰も悪くないです）

まなんだこと

今日は新たに学んだことは特になかったので，自作したトライ(retrieval tree)を載せておきます．（トライについてはWikipediaを参照ください．）

実装したコード

from typing import List, Tuple


class _TrieTreeNode:
    def __init__(self, label: str | None = None) -> None:
        self.label: str | None = label
        self.child: List[_TrieTreeNode | None] = [None for _ in range(26)]


class TrieTree:
    def __init__(self) -> None:
        self.__root: _TrieTreeNode = _TrieTreeNode()
        self.__length: int = 0

    def insert(self, item: str) -> bool:
        current_node = self.__root
        for c in item:
            index = ord(c) - ord("a")
            if current_node.child[index] is None:
                current_node.child[index] = _TrieTreeNode()
            current_node = current_node.child[index]
            assert current_node is not None

        if current_node.label is None:
            current_node.label = item
            self.__length += 1
            return False
        else:
            return True

    def delete(self, item: str) -> bool:
        current_node = self.__root
        stack: List[Tuple[_TrieTreeNode, int]] = []
        for c in item:
            index = ord(c) - ord("a")
            stack.append((current_node, index))
            if current_node.child[index] is None:
                return False
            else:
                current_node = current_node.child[index]
            assert current_node is not None

        if current_node.label is None:
            return False
        current_node.label = None
        self.__length -= 1

        while stack:
            child_node = current_node
            current_node, index = stack.pop()
            if child_node.label is None:
                del child_node
                current_node.child[index] = None
            else:
                break

        return True

    def search(self, item: str) -> bool:
        current_node = self.__root
        for c in item:
            index = ord(c) - ord("a")

            current_node = current_node.child[index]
            if not current_node:
                return False

        return current_node.label is not None

    def enumerate(self, prefix: str = "") -> List[str]:
        current_node = self.__root
        for c in prefix:
            index = ord(c) - ord("a")
            if current_node.child[index] is None:
                return []
            else:
                current_node = current_node.child[index]

            assert current_node is not None

        enumerate_list: List[str] = []
        stack: List[_TrieTreeNode] = [current_node]
        while stack:
            current_node = stack.pop()
            assert current_node is not None

            if current_node.label is not None:
                enumerate_list.append(current_node.label)
            for next_node in reversed(current_node.child):
                if next_node:
                    stack.append(next_node)

        return enumerate_list

    def __len__(self) -> int:
        return self.__length

おわりに

今日みたいなさぼりの日があってもいいよね．
おやすみなさい．