(Swift 实现)AVL树(自平衡搜索二叉树)创建,插入
发布时间:2020-12-14 06:21:08 所属栏目:百科 来源:网络整理
导读:这个实现起来有点难度了,看动画竟然没有摸出什么规律来,插入的方法前面是一样的,后面又做了调整的。好吧,这个我终于看了网上的大神才搞明白Swift的代码如何写出来点这个链接 引言 自平衡二叉树避免了,有的时候二叉搜索树会形成链式结构,就好比,我这一
这个实现起来有点难度了,看动画竟然没有摸出什么规律来,插入的方法前面是一样的,后面又做了调整的。好吧,这个我终于看了网上的大神才搞明白Swift的代码如何写出来点这个链接 引言自平衡二叉树避免了,有的时候二叉搜索树会形成链式结构,就好比,我这一串数字都已经排好序了,从小到大,那按着二叉搜索树,添加的话,都是在右边,右边的右边,那就是个链式结构了,这样就不太好了,所以就想着把它改变改变,于是就有了AVL树。AVL的查找最坏时间复杂度要比二叉搜索树要低,数字越多越低的厉害,O(log N),以2为底。 定义
修正在AVL树,每一个节点都引入了平衡因子的参数(balance factor,以下用BF表示),这个参数表示了这个节点左、右子树的高度差,那么AVL树所有节点的BF(男朋友?)只能是-1,0,1。只要它的绝对值大于1,那左右两边高度相差就有些许远了,那就不平衡了,有这四种情况,我没有总结出来,网上查出来的。(发现个好图)
代码就看上面大神的吧,我自己不好意思贴了 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |