二叉查找树简介
需积分: 0 171 浏览量
2018-01-03
18:04:57
上传
评论
收藏 14KB DOCX 举报
二叉查找树
1，二叉查找树
二叉查找树是一种二叉树结构，它总是保证其右孩子大于根，左孩子小于根，如下：
5
/ \
4 6
这就是一课二叉查找树，当然，他拥有二叉树的性质。
二叉查找树方便查找，对于查找的平均时间复杂度是 logN
为了使得该数据结构存放的数据具有更高的效率，使得二叉树的深度能够更低，那么
就需要平衡二叉树。
2，AVL 树。
AVL 树是一种平衡二叉树，它规定，一颗 AVL 树左子树与右子树的高度最多相差 1，然
而对于 AVL 树的插入，往往会打破原有的平衡条件。这时就需要对二叉树进行调整，这个
调整是通过旋转完成的。对于 AVL 树的插入情况一般存在以下情况：
1) 当某节点的左孩子的左子树进行一次插入（设某节点为 a，那么 a 就是一个左右不
平衡的父节点位置），记为 LL 型
2) 当 a 的右孩子的右子树进行了一次插入，记为 RR 型。
对以上的两种情况只需要进行单旋转就可以恢复平衡，就是反方向旋转一下即可。
3) a 的左孩子的右子树进行一次插入，记为 LR 型
4) a 的右孩子的左子树进行一次插入，记为 RL 型
这里就需要使用双旋转，即先反向再正向即可。
这就是 AVL 树的调整过程。
3，伸展树。
有了对 AVL 树的了解，这里只需要简单的介绍下伸展树就行了。伸展树是一种可以自
我调整的树，总是把当前节点调整到根处。这种调整方式就是与 AVL 一样的采用旋转的方
式进行，知道将当前节点调整到根处为止。伸展树在多次进行查找的平均时间复杂度也是
logN，但是他不用记录树节点的位置等信息，相对 AVL 树更简单。一般的旋转是自外向内
的方式，以能够旋转到根处为止。
4，B 树。
B 树是一种平衡的多叉树数据结构。
评论0
最新资源