Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

二叉树

树形结构,但是树中每个节点的分支最多只有两个,我们叫做二叉树

二叉搜索树(BST)

!> 二叉搜索树又叫二叉排序树,或二叉查找树。它或者是一颗空树或者是具有下列性质的二叉树:

  1. 若它的左子树不为空,则左子树上的所有节点的值均小于它的根节点的值
  2. 若它的右子树不为空,则右子树上的所有节点的值均大于它的根节点的值
  3. 它的左右子树也分别是二叉排序树

平衡二叉树(AVL)

!> 平衡二叉树(self-balancing binary search tree或height-balanced binary search tree)是一颗二叉排序树,其中每个节点的左右子树高度差至多等于1
高度平衡:要么是一颗空树,要么它的左右子树都是平衡二叉树并且左右子树的深度之差的绝对值不超过1。我们将左子树深度减去右子树深度的值称为平衡因子(BF, balance factor)

B树

背景:前面我们讨论的数据结构所处理的数据都是在内存中的,因此考虑的都是内存中运算时间的复杂度。倘若我们操作的数据集非常大,大到内存没法处理怎么办?比如数据库中上千万条记录以及硬盘中的上万个文件等,在这种情况下,对数据的处理需要不断从硬盘等存储设备中调入或调出内存页面。一旦涉及到这样的外存设备,时间复杂度的计算就发生了变化,我们还必须考虑访问外存的时间以及访问外存的次数。

多路查找树也叫B树,其中每个节点的孩子数可以多余两个,且每个节点处可以存储多个元素,由于它是查找树,所有元素之间存在某种特定的排序关系。

例如2-3树,是这样的一颗多路查找树,每个节点都有两个孩子(称为2节点)或三个孩子(称为3节点)
一个2节点包含一个元素和两个孩子,一个3节点包含3个孩子和两个元素
,并且2-3树中所有叶子都在同一层上。

mgBix5

B树是一种平衡的多路查找树,2-3树和2-3-4树都是B树的特例,节点最大的孩子数目称为B树的阶,因此2-3树是3阶B树,2-3-4树是4阶B树

一个m阶的B树具有如下属性:

  1. 如果根结点不是叶结点,则其至少有两棵子树。
  2. 每一个非根的分支结点都有k-1个元素和k个孩子,其中。每一个叶
  3. 子结点n都有k-1个元素,其中。
  4. 所有叶子结点都位于同一层次。
  5. 所有分支结点包含下列信息数据

B+树

评论