Algorithm:BinarySearchTree

Hanaotome wiki

자료구조 알고리즘 중 이진검색트리 (Binary Search Tree)에 대한 문서이다.

목차

개요

Picture 1: Basic binary search tree

이진검색트리(Binary Search Tree)는 다음과 같은 특징을 가진다.

  1. BST의 각 Node는 키값을 하나씩 갖는다. 각 Node의 키값은 중복되어서는 안 된다.
  2. 최상위 레벨에는 Root Node가 있고, 각 Node는 최대 두 개의 자식 Node를 가진다.
  3. 임의의 Node의 키값은 자신의 왼쪽 Subtree의 임의의 키값보다 크고, 오른쪽 Subtree의 임의의 키값보다 작다.