[Swift] Binary Search Tree란? (1)

Binary Search Tree는 (하나의 node가 최대 2개의 자식을 갖는) 트리가 항상 정렬되도록 추가/삭제를 수행하는 binary tree의 한 종류이다. "항상 정렬되어 있다"의 의미는 무엇일까? 위 트리를 봐보자. - parent node : 7 - left child : 2 - right child : 10 node를 기준으로 좌측의 키는 항상 작아야 하며, 우측의 키는 항상 커야한다. 그렇기에 각각의 child들은 정렬되어 있을 수 밖에 없는 것이다. (child의 child 또한 마찬가지) Insert 그렇다면 기존 트리에 새로운 node를 추가할 때는 어떻게 해야할까? 먼저 새로운 node 값을 추가할 때 roott node(최상단)의 값과 비교한다. 만약 새로 추가하고자 하는 값이 ..