From: https://answers.yahoo.com/question/index?qid=1006050403204

通常假设BST没有重复元素。有重复元素的情况需要了解一下: 可以插入不同node(同时插入左右或只插入一边。注意此时BST property情况比较微妙。此时一个主要影响是BST可能较难保持平衡性), 或同一node有counter计数有多少重复(multiset)。

a binary search tree (BST) is a binary tree which has the following properties:

Each node has a value.

The left subtree of a node contains only values less than or equal to the node's value.

The right subtree of a node contains only values greater than or equal to the node's value.

The major advantage of binary search trees is that the related sorting algorithms and search algorithms can be very efficient, like in-order traversal.

Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays.

We may or may not choose to allow duplicate values in a BST; if we do, it represents a multiset, and inequalities for the left and right subtrees above are non-strict (they have or equal to). If we do not, the inequalities can be taken as strict, and insertion operations must be modified to fail if the value being inserted is already present; in this case the BST represents a set with unique values, like the mathematical set. Yet other definitions use a non-strict inequality on only one side, which allows duplicate values but limits how well a tree with many duplicate values can be balanced.