本篇内容主要讲解“如何通过代码实现二叉搜索树”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“如何通过代码实现二叉搜索树”吧!
首先,二叉搜索树到底是什么?
二叉搜索树(BST)是一种特殊类型的树形数据结构,由节点及其子节点组成,子节点也被视作“后代”,可以把它想象成一棵倒置的树或者是树的根部。
每个节点最多只能有2个子节点:左节点和右节点。为了使它成为一个有效的二叉搜索树,左节点的值必须总是小于母节点,而右节点的值必须总是大于母节点。没有任何间隙的BST,即每个节点都有一个左节点和一个右节点的二叉搜索树,被称为“完美”树。
在完美树中,当遍历树时,每个级别中的节点数会翻倍,将前面的所有节点相加并在该数字上再添加“1”可以得出底层的节点总数。
当在平衡二叉搜索树中搜索一个元素时,平均需要花费额的时间为O(log n),在最坏的情况下,需要O(n)。你可以把在二叉搜索树中的搜索看作是“选择你自己的冒险”模型,从顶部节点开始,然后沿着树向下,在到达的每个节点问同样的2个问题。
我要找的值是否小于当前节点?如果是,向左走。
我要找的值是否大于当前节点?如果是,向右走。
插入和删除也非常快,平均花费O(log n)的时间。但有一个缺点就是不能像数组那样获得随机元素。
什么时候可以使用二叉搜索树?
假设你需要为Facebook这样的社交媒体应用程序设计一个数据库。该数据库需要处理数百万个用户名,并且需要在登录期间快速检索到其中一个用户名。由于每天都有新注册或删除的账户,你也需要方便进行插入和删除的操作。
通过一个排序过的数组进行二分搜索会非常快(需要花费O(log n)时间),但是插入或删除一个用户名会导致整个数组重新排序,需要花费O(n)时间,这取决于数组的大小,可能会相对慢一些。如果我们使用二叉搜索树,插入或删除的时间会快得多(花费O(log n)时间)。
如果有一个带有名字的二叉搜索树(比如这个《海底总动员》的树),就可以按字母顺序排列。
在字母表中,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了!
效率很高。二叉搜索树减少了整个搜索过程的时间复杂性!如果树没有分类,只是一个普通的树形结构呢?或者要证实这是个二叉搜索树呢?目前有两种不同的搜索技术可以实现这一点。
什么是广度优先搜索?
广度优先搜索是一种在树(或图形)中一次遍历一级的方法,每次都从左到右在节点之间移动。
在《海底总动员》的例子中,Marlin首先会问Dory,“你知道我儿子Nemo在哪里吗?”如果它说不,Marlin就会问Moonfish同样的问题。如果它也说不,Marlin会再下一层,问Crush、Gill和Mr. Ray,然后Marlin就找到Nemo了!
广度优先搜索
如果在Mr. Ray之后没有找到Nemo,Marlin会到下一级询问Bruce和Darla等等。使用广度优先搜索可以找到起始节点(Marlin)和目标节点(Nemo)之间的最短距离。时间复杂度是O(n),因为在最坏的情况下,需要检查每个节点才能找到Nemo。
什么是深度优先搜索?
深度优先搜索(Depth first search)是一种从顶部节点一直向下遍历到其最远子节点的树(或图形)的方法,然后在未找到目标节点时再回去并尝试其他路径。
在《海底总动员》的例子中,Marlin首先会问Dory “你知道Nemo在哪里吗?” 如果她不知道,他就会问Crush同样的问题,因为Crush是Dory最左边的子节点。如果Crush也说没有,Marlin将移动到下一级去问Bruce,尽管他害怕成为鲨鱼的点心,但也会问问他有没有见到自己的儿子。
深度优先搜索
如果Bruce说没看到Nemo,并向Marlin保证“鱼是朋友,不是食物”,Marlin就需要回到上级,寻找另一个他还没有问到的节点。回到Crush那里,他会发现下一步应该问Darla。由于Crush的所有后代现在都被审问过了,Marlin会回到Dory那里,检查她其余的“后代”。Marlin需要把每个角色询问一遍后才能找到Nemo。
深度优先搜索顺序
与广度优先搜索一样,深度优先搜索也包括时间复杂度O(n),但空间复杂度可能有所不同。深度优先搜索通常占用较少的内存或空间,假设可以在遍历整个树之前找到目标节点。
由于二叉搜索树中的每增加一级节点会加倍(至少对于平衡树而言),如果丢失的节点(Nemo)位于树的较低位置,则可以使用深度优先搜索来节省内存。在最坏的情况下,两种方法的空间复杂度都是O(n)。
关于二叉搜索树以及如何通过代码实现它们还有很多需要学习,但这个有趣的案例会成为你了解数据结构的起点。
到此,相信大家对“如何通过代码实现二叉搜索树”有了更深的了解,不妨来实际操作一番吧!这里是编程网网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!