[Python]트리 구조

Tree

• 데이터 사이의 계층 관계 표현
• 노드 와 가지 로 구성
• 루트 : 트리의 가장 위쪽에 있는 노드
• 리프 : 가장 아래쪽에 있는 노드
• 자식 : 어떤 노드와 가지가 연결되었을 때 아래쪽에 있는 노드
• 부모 : 어떤 노드와 가지가 연결되었을 때 위쪽에 있는 노드
• 형제 : 부모가 같은 노드
• 자손 : 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드
• 레벨 : 루트에서 얼마나 멀리 떨어져 있는지를 나타낸다
• 차수 : 각 노드가 갖는 자식의 수
• 높이 : 루트에서 가장 멀리있는 리프까지의 거리
• 서브트리 : 어떤 노드를 루트로 하고 그 자손으로 구성된 트리

노드 스캔 방법

• 너비 우선 검색(breadth first search)
• 깊이 우선 검색(depth first search)

이진 검색 트리

• 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리

from __future__
from typing import Any,Type

class Node:
    def __init__(self,key: Any, value: Any, left: Node = None,right: Node = None):
        self.key = key
        self.value = value
        self.left = left
        self.right = right

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

    def search(self,key: Any) -> Any:
        p = self.root
        while True:
            if p is None:
                return None
            if key == p.key:
                return p.value
            elif key < p.key:
                p = p.left
            else:
                p = p.right