Binary Search Trees - 二叉查找树

定义：

一颗二叉查找树(BST)是一颗二叉树，其中每个节点都含有一个可进行比较的键及相应的值，且每个节点的键都大于等于左子树中的任意节点的键，而小于右子树中的任意节点的键。

二叉查找树使用的每个节点含有两个链接，它是将链表插入的灵活性和有序数组查找的高效性结合起来的高效符号表实现。

二叉树中每个节点只能有一个父节点(根节点无父节点)，只有左右两个链接，分别为左子节点和右子节点。

基本实现

节点包含

• 一个键
• 一个值
• 一条左链接
• 一条右链接
• 一个节点计数器(以该节点为根的子树的节点总数，包含自身)