实现良好的数据库设计
|
效率很高。二叉搜索树减少了整个搜索过程的时间复杂性!如果树没有分类，只是一个普通的树形结构呢?或者要证实这是个二叉搜索树呢?目前有两种不同的搜索技术可以实现这一点。 什么是广度优先搜索? 广度优先搜索是一种在树(或图形)中一次遍历一级的方法，每次都从左到右在节点之间移动。
在《海底总动员》的例子中，Marlin首先会问Dory，“你知道我儿子Nemo在哪里吗?”如果它说不，Marlin就会问Moonfish同样的问题。如果它也说不，Marlin会再下一层，问Crush、Gill和Mr. Ray，然后Marlin就找到Nemo了! 如果有一个带有名字的二叉搜索树(比如这个《海底总动员》的树)，就可以按字母顺序排列。 在字母表中，Dory在Marlin之前，所以它是左边的节点，而Moonfish在Marlin之后，所以它是右边的节点。同样地，在下一层搜索也遵循这个规律。Bruce在Crush之前，也在Dory和Marlin之前。Darla在Crush之后，但在Dory和Marlin之前。 现在准备好，是时候寻找Nemo了! 寻找Nemo! 假设已经有一个有效的二叉搜索树，并且需要找到Nemo。因为我们知道树中的节点是按字母顺序排序的，所以这应该相当简单。
从Marlin开始，左边是Dory，右边是Moonfish。我们知道Nemo在字母表中位于Marlin之后，所以我们将遍历到正确的节点(Moonfish)。Nemo按字母顺序是排在Moonfish之后的，所以继续往下看Moonfish的右子节点。很幸运，那是…Nemo!找到Nemo了! 当在平衡二叉搜索树中搜索一个元素时，平均需要花费额的时间为O(log n)，在最坏的情况下，需要O(n)。你可以把在二叉搜索树中的搜索看作是“选择你自己的冒险”模型，从顶部节点开始，然后沿着树向下，在到达的每个节点问同样的2个问题。
插入和删除也非常快，平均花费O(log n)的时间。但有一个缺点就是不能像数组那样获得随机元素。 什么时候可以使用二叉搜索树? 假设你需要为Facebook这样的社交媒体应用程序设计一个数据库。该数据库需要处理数百万个用户名，并且需要在登录期间快速检索到其中一个用户名。由于每天都有新注册或删除的账户，你也需要方便进行插入和删除的操作。
通过一个排序过的数组进行二分搜索会非常快(需要花费O(log n)时间)，但是插入或删除一个用户名会导致整个数组重新排序，需要花费O(n)时间，这取决于数组的大小，可能会相对慢一些。如果我们使用二叉搜索树，插入或删除的时间会快得多(花费O(log n)时间)。 （编辑：广安站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
