查找 排序 - yingziaiai/SetupEnv GitHub Wiki

http://www.iqiyi.com/v_19rrhzypgw.html 视频

总是出现在我的页面中，什么搜索，查找，排序， JAVA中集合，数组等等，什么树，图，二叉树等，而且之前可以转换，我就经常云里雾里的，今天下定决定要搞清楚： http://www.iqiyi.com/v_19rrhzypgw.html

谈到树，应该最就是普通树，然后有特殊情形的树，比如二叉树等概念 一般处理问题的思维，就是由大化小，由繁化简，由一般到特殊，于是我们在数学课上常分析的是等差等比数列，分布中最常分析的是均匀分布等有规很的问题的研究；然后把复杂的问题转化为这些可按规律解决的子问题。

常用的概念有：图，森林，树。

图：http://blog.chinaunix.net/uid-26548237-id-3482778.html

树是任意两个顶点间有且只有一条路径的图。或者说，只要没有回路的连通图就是树。

森林是指互相不交并树的集合。

树图广泛应用于计算机科学的数据结构中，比如二叉查找树，堆，Trie树以及数据压缩中的霍夫曼树等等。

二叉树：（二叉树－》二叉查找树，二叉堆）－－百度百科 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。 二叉树常被用于实现二叉查找树和二叉堆。 ｛ 完全二叉树 满二叉树 平衡二叉树 ｝ 同是二叉树，都有其相互间的区别，但也有最基础的共性即二叉树的性质，也有存储结构（顺序存储与链表存储）

http://www.cnblogs.com/iyjhabc/archive/2012/11/05/2987471.html

以上将二叉树区分为完全二叉树，满二叉树，平衡二叉树是从存储结构上来定义的，并未涉及到每个节点之间的大小等，于是当涉及大小时，又有如下划分：

二叉堆是一种近似的完全二叉树，二叉堆满足二叉树的性质。除此之外，二叉堆对于节点的大小关系是有一定要求的。二叉堆的子节点都比根节点大（或者都比根节点小）。算是一种特殊的完全二叉树。

二叉堆用于堆排序，但不意味着二叉堆就是堆排序，只是堆排序利用了二叉堆的优良性质。

二叉堆是一种特殊的堆，二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。二叉堆有两种：最大堆和最小堆。最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。

既然涉及大小，那么在对象的概念里，它就有一些操作，以满足无论是增删改查其始终是二叉堆。 二叉堆一般用数组来表示。例如，根节点在数组中的位置是0，第n个位置的子节点分别在2n+1和 2n+2。因此，第0个位置的子节点在1和2，1的子节点在3和4。以此类推。这种存储方式便於寻找父节点和子节点。

二叉查找树（二叉搜索树，二叉排序树）就是一种更加普遍的二叉树，它不局陷于仅对以上三种特殊二叉树之间节点的大小运算： 二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

二叉查找树算法实现 1 二叉排序树的查找算法 2 在二叉排序树插入结点的算法 3 在二叉排序树删除结点的算法 4 二叉排序树性能分析

而平衡二叉树则是一种不仅要有结构，还要有大小规定的树，二叉查找树则仅关注是二叉树且有大小即可；所以平衡二叉树的操作中不仅仅有操作数据的操作，还有调节数据位置的操作以保证始终维持为平衡二叉树的结构。

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法）

且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。构造与调整方法 平衡二叉树的常用算法有红黑树、AVL、Treap等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

正如上描述，为了维持树的平衡，以及大小，实现这样的需求的算法有多种，目前比较成熟常见的有AVL

对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度（O(log2n)）同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。 平衡二叉搜索树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O（log（n）），大大降低了操作的时间复杂度。

到于Ｂ树（B+,B-,B*)就都是对多路树而言 http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html

上述在此文比较清晰：

http://blog.sina.com.cn/s/blog_54eb9d9e0102w7lb.html

http://blog.csdn.net/sup_heaven/article/details/39313731

而哈夫曼树的应用场景就与上述都不同，主要而涉及到图相关概念中的边权值

https://my.oschina.net/lock0818/blog/492426

二叉排序树的基本实现：

http://blog.csdn.net/jackfrued/article/details/10129649

号称讲得最清晰的二叉树算法： http://blog.csdn.net/yang_yulei/article/details/26066409

http://www.tuicool.com/articles/juyQRz

树转为二叉树：－－－http://blog.csdn.net/sddxqlrjxr/article/details/51084698 1、树转换为二叉树

由于二叉树是有序的，为了避免混淆，对于无序树，我们约定树中的每个结点的孩子结点按从左到右的顺序进行编号。

将树转换成二叉树的步骤是： （1）加线。就是在所有兄弟结点之间加一条连线； （2）抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线； （3）旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。

中文的定义一般空洞而晦涩，这个文章例子与英文描述特别清晰 http://courses.cs.vt.edu/~cs3114/Spring10/Notes/T03a.BinaryTreeTheorems.pdf

平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

那么首先有哪几种特殊的树呢？各自的特点与适用场景又是怎样的呢？然后它们之间可以转化吗？其它一般问题又如何向它们转化呢？

此文给出了各种对节点大小有约定的数据结构的代码测试： http://blog.csdn.net/zhongweijian/article/details/8167304

上述是关于树中的概念与存储：并且是对树中每一个节点而言的一种大小约束，而不涉及整体的排序，整体的排序算法有 关于海量数据查找排序问题 http://blog.csdn.net/lixam/article/details/8845310－－－平时可以思考，这与算法关联的应用场景

http://www.cnblogs.com/edwinchen/p/4788541.html

http://www.cr173.com/html/15301_all.html

http://www.cr173.com/up/2012-5/2012051109471558240.png 排序： ｛内部排序：插入－直接插入与希尔，选择－简单选择与堆，交换－冒泡与快速，归并，基数 ｛外部排序： 这篇文章好在让人容易记住名字的原因，也能map上思想与算法名，但缺少算法实现。－－http://www.cr173.com/html/15301_all.html http://www.jianshu.com/p/8c915179fd02---超好

http://blog.csdn.net/sc6231565/article/details/25653349

但理清了这些关系，不禁还是想问，它们各自的应用场景是什么，如何选取呢？

用的最多的应该是平衡二叉树，有种特殊的平衡二叉树红黑树，查找、插入、删除的时间复杂度最坏为O(log n) Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。 还有哈夫曼树编码方面的应用。 B-Tree，B+-Tree在文件系统中的应用 红黑树还有nginx定时器呀... B-树是多叉树 链接：https://www.zhihu.com/question/29263118/answer/58772633

http://www.cnblogs.com/edwinchen/p/4788541.html－－这个博主似乎都在研究这些排序

高中数学 http://www.pep.com.cn/gzsx/xszx_1/sxjs/gzsxjsjz/201008/t20100827_777107.htm

等差数列求和公式推导  求和推导 证明：由题意得：  Sn=a1+a2+a3+。。。+an①  Sn=an+a（n-1）+a（n-2）+。。。+a1② ①+②得：  2Sn=[a1+an]+[a2+a(n-1)]+[a3+a(n-2)]+...+a1+an Sn={[a1+an]+[a2+a(n-1)]+[a3+a(n-2)]+...+[a1+an]}/2  Sn==n（A1+An）/2 (a1，an，可以用a1+（n-1）d这种形式表示可以发现括号里面的数都是一个定值，即A1+An）

等比数列的推导

Sn=a1+a2+……+an  qSn=a1q+a2q+……+anq=a2+a3+……+a(n+1)  Sn-qSn=a1-a(n+1)=a1-a1q^n (1-q)Sn=a1(1-q^n)  Sn=a1*(1-q^n)/(1-q) 

换底公式 https://ss1.baidu.com/6ONXsjip0QIZ8tyhnq/it/u=506614216,773713317&fm=58 公式描述：公式中a，c均大于零且不等于1。