二叉排序树是 由树到索引

在之间介绍数据结构的文章中我们介绍过二叉树查找，如果忘记的大家可以查看下这篇文章数据结构-树的那些事(四)，这里对二叉树就不做介绍，我们来说一下二叉排序树；

二叉排序树(Binary Search Tree):又被称为二叉查找树或者二叉搜索树，当然首先是二叉树，另外特点如下：

1.若它的左子树不为空，则左子树的结点小于它根节点的值；

2.若它的右子树不为空，则右子树的结点大于它根节点的值；

3.它的左、右子树也分别为二叉排序树；

明白特点接下来我们来说一下查找的性能，二叉排序树查找性能取决于二叉树的形状，但是二叉树排序的形状是不确定，最坏的情况查找性能为O(n)，最好情况查找性能为O(logn)，如下图

接下来我们谈一下二叉排序树的增加和删除操作，查询就没必要说明，就写下代码实现下就好；

增加操作:

1.若当前的二叉树排序树为空，则插入元素的根节点；

2.若插入的值小于根节点，则插入到左子树当中；

3.若插入的值大于根节点，则插入到右子树当中；

删除操作：

1.若删除的是子节点，则直接删除该结点；

2.若删除的节点仅有左或者右子树的结点，则让该结点的子树与父亲节点相连，删除该结点即可；

3.若删除的节点左子树和右子树都有子结点，如下面两幅图，这里面强调一下第二幅图，删除47以后用37或者48都可以满足二叉排序树，这里我们为什么选择47而要放弃37，是因为二叉排序树按照中序遍历以后形成的是一个有序序列(由小到大排序)，选择37以后不满足这个特征；

上面我们谈到二叉排序树性能问题，接下来我们来说一下平衡二叉树看如何处理二叉树性能问题，所有代码在介绍完成以后提供实现；

平衡二叉树(AVL树):首先平衡二叉树是一颗二叉树排序树，他的特点是每一个节点左子树和右子树的高度差至多等于1,这样就能避免照成单枝树，影响查询效率,来个看图识AVL树，下图中图二满足二叉排顺序树的特征，58节点的左子树大于59，图三58的左子树的高度为2，右子树的高度为0，高度差大于1，所以不满足平衡二叉树，接下来我们谈谈平衡二叉树插入和删除照成失衡以后的操作(平衡二叉树的旋转)。

失衡以后操作:

失衡以后可能造成4种情况:LL(左左)、RR(右右)、LR(左右)、RL(右左)，接下来我们用图说话,看一下这4种情况；

对这4种情况进行统一整理就是：插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。就用第一种说一下当插入D的时候导致，导致5左子树的高度为3，5的右子树为1，差值大于1，这个时候我们抓住3，使5进行右旋，3的右孩子变成5的左孩子这个时候平衡达成。

这里简单讲一下对应结点的抽象，不同于二叉树的情况就是这里要增加一个高度的属性，好用来判断左子树和右子树的差值；

B树:首先要明白B树要处理什么问题，我们上面提到过的AVL树、二叉排序树以及我们没有提到过的红黑树，这些都是在内存中内部查找树，而B树是前面平衡树算法的扩展，它支持保存在磁盘或者网络上的符号表进行外部查找，这些文件可能比我们以前考虑的输入要大的多（难以存入内存）。既然内容保存在磁盘中，那么自然会因为树的深度过大而造成磁盘I/O读写过于频繁（磁盘读写速率是有限制的），进而导致查询效率低下。那么降低树的深度自然很重要了。因此，我们引入了B树，多路查找树。

明白了B树是干什么用的，我们来个他下个定义，B树是一种平衡的多路查找树，结点最大的孩子数目为B树的阶，一个m阶的B树特征如下：

1.每个根节点至少有2个孩子节点；

2.每个非根的分支节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m；

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-68999-1.html