大门| 2008年大门|问题12

以下哪项是正确的？

（A） 搜索AVL树的代价是θ（logn），而二叉搜索树的代价是O（n） （B） 搜索一棵AVL树的代价是θ（logn），而完整二叉树的代价是θ（nlogn） （C） 二叉搜索树的搜索代价是O（logn），而AVL树的搜索代价是θ（n） （D） 搜索AVL树的代价是θ（n logn），而二叉搜索树的代价是O（n） 答复: （A） 说明： AVL树是一种平衡树。 AVL树的搜索时间复杂度=θ（logn） 但二叉搜索树可能是斜树，所以在最坏的情况下，BST搜索时间=θ（n） 这个问题的小测验