A22031. $在⼆叉排序树（Binary Search Tree, BST）中，假设节点值互不相同。给定如下搜索函数，以下说法⼀定正确的是（）。bool find(Node* root, int x) { while (root) { if (root->val == x) return true; root = (x < root->val)? root->left : root->right; } re\dots$

单选题困难

知识点

二叉排序树查找算法迭代

题目描述

在⼆叉排序树（Binary Search Tree, BST）中，假设节点值互不相同。给定如下搜索函数，以下说法⼀定正确的是（ ）。 bool find(Node* root, int x) { while (root) { if (root->val == x) return true; root = (x < root->val)? root->left : root->right; } return false; }

最坏情况下，访问结点数是O(log n)

最坏情况下，访问结点数是O(n)

⽆论如何，访问结点数都不超过树⾼的⼀半

⼀定⽐在普通⼆叉树中搜索快

上一题下一题