在平衡二叉树中搜索项目
Searching an item in a balanced binary tree
如果我有一棵平衡二叉树，我想在里面找一个项目，大O时间复杂度是O(n)吗？是否会在二叉树中搜索一个项目，而不管它是否平衡会改变 O(n) 的大 - 哦时间复杂度？我知道如果我们有一个平衡的 BST 那么搜索一个项目就等于 BST 的高度所以 O(log n) 但是普通的二叉树呢？
平衡 BST 中的 O(log n) 搜索时间由两个属性促成：
- 树中元素比较排列
- 树是（大约）平衡的。
如果您丢失了其中任何一个属性，那么您将不再获得 O(log n) 搜索时间。
如果您正在为特定值搜索未排序的平衡二叉树（又名不是 BST），那么您将必须检查树中的每个节点以确保找到您要查找的值，所以它需要 O(n) 时间。
对于一棵不平衡的树，如果您想象最坏的不平衡情况可能会有所帮助，在这种情况下，每个节点只有一个子节点，叶子除外——本质上是一个链表。如果你有一个完全（或大部分）不平衡的 BST，搜索将花费 O(n) 时间，就像链表一样。
如果未排序的二叉树是不平衡的，它仍然有n个节点，它们仍然是未排序的，所以仍然需要O(n)的时间。
如果我有一棵平衡二叉树，我想在里面找一个项目，大O时间复杂度是O(n)吗？是否会在二叉树中搜索一个项目，而不管它是否平衡会改变 O(n) 的大 - 哦时间复杂度？我知道如果我们有一个平衡的 BST 那么搜索一个项目就等于 BST 的高度所以 O(log n) 但是普通的二叉树呢？
平衡 BST 中的 O(log n) 搜索时间由两个属性促成：
- 树中元素比较排列
- 树是（大约）平衡的。
如果您丢失了其中任何一个属性，那么您将不再获得 O(log n) 搜索时间。
如果您正在为特定值搜索未排序的平衡二叉树（又名不是 BST），那么您将必须检查树中的每个节点以确保找到您要查找的值，所以它需要 O(n) 时间。
对于一棵不平衡的树，如果您想象最坏的不平衡情况可能会有所帮助，在这种情况下，每个节点只有一个子节点，叶子除外——本质上是一个链表。如果你有一个完全（或大部分）不平衡的 BST，搜索将花费 O(n) 时间，就像链表一样。
如果未排序的二叉树是不平衡的，它仍然有n个节点，它们仍然是未排序的，所以仍然需要O(n)的时间。