上学的时候是学过数据结构的。。可是对于二叉树，提起来总是一脸懵逼。总是看着黑板上一堆圈圈杠杠。。什么前序，中序，后续遍历，很是莫名。。我在想这到底在干什么？？？因此埋下坑，最近看java基础，发现一些红黑树的应用，对二叉树若有所悟。
首先二叉树结构的基本参数，自己（节点），父节点，左子节点和右子节点；
然后来看二叉树能干什么；来说说我是怎么发现的，因为之前对这个概念一直很模糊。。
首先，set和treeSet的区别，treeSet是有序的，然后map和TreeMap的区别，TreeMap是有序的，因此我认为Tree就是个排序方法；
那怎么排序呢，要排序肯定对象实现了比较方法comparable，然后二叉树结构就是最简单的，N个对象比大小，第一个就是父节点，然后第二个数如果比第一个小就是左子树，比第一个大就是右子树，依次类推。。
说完二叉树，再说java为什么要用红黑树，所谓红黑树就是平衡二叉树的特殊实现，二叉树为什么要平衡呢？
举例，如果N个数是从小到大的。。那个二叉树结构不就成了一条斜线吗。。如果要找其中一个数，岂不是要把每个节点都过一遍。。
所以平衡二叉树要做的是让根节点左右边的节点数差不多。
比如一条直线的二叉树，如果从中间折断，它依然满足左边小，右边大的基本特性，但是如果查询一个值，至少我们可以减少一半的查询效率；因为中间这个数是中间值，如果x比中间值大，那么这个数肯定在右边，反之亦然
当然这种平衡二叉树数据结构的增删改查的效率是比不上链表，但要保证数据的有序性，还要算上效率，那平衡二叉树非常nice
既然平衡二叉树已经如此优秀，那么红黑树又是为什么出现呢？
我们在实现平衡二叉树时，随着数据量的增大，有时一个子节点的增加可能会让整个树发现大范围的翻转，那么如果标识红的子节点是黑，黑的子节点是红，将二叉树一层层分开，为了满足红黑树的特性，平衡二叉树必然不能发生大范围翻转，缺点是红黑树的查询速率没有平衡树高，但是修改，删除操作远优于平衡二叉树
再说说前种后序遍历，既然二叉树是有序的，那我们就把一串数字按从小到大输出，或者从大到小输出。。但是直接一串数想不出来，网上随便找个图
先序 abdefcghi
中序 dbefaghci
后序 defbhgica
如果满足大小关系 ，那么有 B<A,D<B,F>B,E<F,C>A,G<C.I>C,H>G
再说推断关系，D和E谁更小，如果E<D那么E应该是D的左子节点，然后不是，说明D<E；
那么，正确的从小到大的顺序是DBEFAGHC 即是二叉树的中序遍历
至于先序和后序，我倒是没什么想法，百度后，发现先序用来展示文件夹结构,如果用来展示文件夹，a下面有bc，但是b下还有文件，所以先不展示c,b下面有df,f下有e所有先e后f,再之后是本该是c可c下还有g，g下还有h，所以为ghc，最后是g平级的i
后序是用来计算文件大小,这个暂时理解不了，可能展示了自底向上的一种统计方式吧。。
至于红黑树具体怎么实现，https://www.cnblogs.com/skywang12345/p/3624343.html这篇文章讲的非常清楚
网友评论