二叉搜索树解释
Binary Search Tree Explanation
我想复习一下我对二叉树，尤其是二叉搜索树的理解。通过维基百科向我展示了以下信息 (http://en.wikipedia.org/wiki/Binary_search_tree)：
"Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees. On average, this means that each comparison allows the operations to skip over half of the tree, so that each lookup/insertion/deletion takes time proportional to the logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an unsorted array, but slower than the corresponding operations on hash tables."
有人可以详细说明/解释该描述的以下部分吗：
1) "On average, this means that each comparison allows the operations to skip over half of the tree, so that each lookup/insertion/deletion takes time proportional to the logarithm of the number of items stored in the tree."
2) [从最后一句]“......但比哈希表上的相应操作慢。”
1) "On average"仅适用于BST 平衡，即左右子树包含大致相等数量的节点。这使得搜索成为一个 O(log n) 操作，因为在每次迭代中，您可以粗略地丢弃剩余项目的一半。
2) 在哈希表上，查找、插入和删除都需要 O(1) 时间。
我想复习一下我对二叉树，尤其是二叉搜索树的理解。通过维基百科向我展示了以下信息 (http://en.wikipedia.org/wiki/Binary_search_tree)：
"Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees. On average, this means that each comparison allows the operations to skip over half of the tree, so that each lookup/insertion/deletion takes time proportional to the logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an unsorted array, but slower than the corresponding operations on hash tables."
有人可以详细说明/解释该描述的以下部分吗：
1) "On average, this means that each comparison allows the operations to skip over half of the tree, so that each lookup/insertion/deletion takes time proportional to the logarithm of the number of items stored in the tree."
2) [从最后一句]“......但比哈希表上的相应操作慢。”
1) "On average"仅适用于BST 平衡，即左右子树包含大致相等数量的节点。这使得搜索成为一个 O(log n) 操作，因为在每次迭代中，您可以粗略地丢弃剩余项目的一半。
2) 在哈希表上，查找、插入和删除都需要 O(1) 时间。