堆
二叉查找树

堆

堆是一种图的树形结构，被用于实现“优先排列”。优先排列是以一种数据结构，可以自由的添加数据，但取出数据时要从最小值开始按顺序取出。在堆的树形结构中，各个顶点被称为结点，数据就存在这些结点中。
堆中每个结点最多有两个子结点，同一行里则为从左到右。在堆中存储数据必须遵守一条准则：子结点必定大于父结点，因此最小值被存储在顶端的根结点中。往堆中添加数据的时候，为了遵守这个准则，一般会把新数据放到最下边一行靠左的位置，当最下边一行没有多余位置的时候，就向下另起一行，把数据加在这一行的最左边。
从堆中取出数据的时候，取出的是最上边的数据，这样堆中就能始终保持最上边的数字最小。取出顶端数据以后，将最新添加的数据移动到最顶端，然后重新排序，依次将父结点跟数字比较小的子结点进行交换。

从堆中取出最小值的时间复杂度都为o(1)，重新排序的话，重构树所要运行的时间跟树的高度成正比，重构树的时间复杂度为o(log n)。
添加数据要从下到上依次比较，所以你时间复杂度也是o(log n)。

二叉查找树

二叉查找树也采用了图的树形结构。二叉查找树有两个性质，一是每个结点的值均大于其左子树上任意结点的值，二是每个结点的值均小于其右子树上任意一个结点的值。根据这两个性质可以得到几个推论。首先，二叉查找树的最小结点要从顶端开始，往其左下的末端查找，反过来，要查找最大值的时候，也要从顶端开始，往其右下的末端查询。
要添加数据的时候，从顶端开始，依次向下比较，如果比结点保存的数据小，那么向左边子树查询，如果比结点保存的数据大，那么向右边子树查询，直到查找到没有结点为止，将新结点添加到该位置为止。
删除数据的时候，如果没有子结点，那么直接删除该结点，如果只有一个子结点，那么将子结点移动到该结点的位置，如果有两个子结点的话，那么在被删除的左子树中寻找最大结点，然后将最大子结点移动到被删除的结点的位置上，如果最大子结点还有子结点，那么按照之前的操作执行就好了。
查找的话，从顶端开始，如果小于结点中的数据，那么向左查找，如果大于结点中的数据，那么向右查找。
在查找数据或者添加数据的时候，需要和现有的数据比较，比较的次数取决于树的高度，如果树形状比较均衡的话，那么时间复杂度为o(log n)，如果树的结构偏向一侧的话，树的高度会很高，时间复杂度为o(n).

    有一些以二叉查找树为基础扩展的数据结构，比如平衡二叉树：这种数据结构可以修正形状不均衡的树用以提高查找效率。
    另外，虽然二叉查找树中有一个结点最多只有两个子结点，但我们可以把子结点扩展为m（m为预先设定的常数）。像这种子结点数可以自由设定，并且形状均衡的树便是B树。