Binary Search Tree

• Binary: 두갈래로 갈라지는

• Tree graph: node, edge 로 이루어진 그래프

• 숨덩숨덩 가지치기가 가능하기 때문에 매우 빠르게 원하는 것을 찾을 수 있음

       | node                            | tree 
-------------------------------------------------------------
depth  | # edges from node to root       | -
-------------------------------------------------------------
height | # edges of longest path to leaf | hight of root

출처: https://stackoverflow.com/questions/2603692/what-is-the-difference-between-depth-and-height-in-a-tree

• OCaml에서 트리 타입을 사용하려면:
  type 키워드를 통해 트리의 구조를 미리 정의해야 함.
  OCaml과 같은 정적 타입 언어에서 중요한 과정으로,
  컴파일러가 각 데이터 구조의 타입을 미리 알고 있어야 하기 때문.

type 'a bstree = 
 | Leaf 
 | Node of 'a * 'a bstree * 'a bstree

on the other hand,
파이썬 같은 동적 타입 언어에서는 타입을 미리 정의할 필요가 없음.
파이썬에서는 클래스나 리스트, 딕셔너리 등을 이용해 트리 구조 구현 가능.
ex: 파이썬에서 이진 트리를 클래스 기반으로 정의하면

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