北京中科白瘕风医院是正规 http://wapyyk.39.net/bj/zonghe/89ac7.html前一篇我们讲了数组、链表、队列、栈、跳表、散列表这6种数据结构，这其实讲的是数据结构中的数据逻辑结构，是一系列数据在逻辑上的组织方式，通过不同的逻辑组织方式，一系列数据的项与项之间就存在了某种逻辑关系，而我们也正是通过这样的逻辑关系达到我们更好操作数据的目的。
而数据结构还有一种分类就是物理结构，也叫存储结构，汇总下：
逻辑结构物理结构集合顺序存储线性结构（数组、链表、栈、队列等）链式存储树形结构（二叉树、红黑树、B树、B+树等）索引存储图形结构哈希存储......
对于数据的操作一般有：插入、删除、查找（单个、范围）、排序、遍历等。
每种数据结构的特点汇总：
数组
大小固定、内存连续、支持下标随机查找，插入、删除低效，按值查找低效
链表插入、删除高效、查找低效栈链式（基于链表）或者顺序（基于）存储，先进后出，固定端口队列链式（基于链表）或者顺序（基于）存储，先进先出，一端入队、一端出队跳表链表+索引，链表的基础上借助索引提高查询效率，插入删除时需要维护索引层散列表数组+链表，k-v格式，f(key)散列函数得到数组的下标，根据下标得到链表的头指针，插入、删除，单个查找高效，不支持范围查找
一种数据结构的逻辑结构根据需要可以表示成多种存储结构。
今天一起学习下树形结构。
树
顾名思义，数据的逻辑结构呈树状，树中涉及的名词有：根节点、父子节点、兄弟节点、叶子节点，树的高度、深度、层。举例说明：
根节点：a节点
父子节点：a和b、a和c节点为父子节点，a为父节点，bc为子节点
兄弟节点：b和c节点为兄弟节点
叶子节点：没有子节点的节点为叶子节点，d和e就是叶子节点
高度：从上往下，由高到低，分别是2、1、0
深度：从下往上，由高到低，分别是2、1、0
层：深度+1，从下往上，由高到低、分别是3、2、1
树的高度：根节点的高度2
二叉树
顾名思义，每个节点最多有2个子节点，前面的图就是一个二叉树。根据二叉树节点的规则，又可以得到满二叉树、完全二叉树等。如下：
满二叉树的特点有两个：1、叶子节点全部在最大层2、非叶子节点都有2个节点。
完全二叉树的特点有两个：1.除去最后一层节点，就是一个满二叉树。2.最后一层至少存在左节点。如果存在右节点，则必须同时存在左节点。
这么来看的话，其实满二叉树属于完全二叉树里的一种特殊。
二叉树的存储一般有两种方式：顺序和链式存储。
链式存储：类似链表，节点的组成如下：
left-data-right
知道根节点即可串起整棵树，大部分二叉树就是这种数据结构。
顺序存储：基于数组，比如i下标存储根节点，那么2*i的位置存储左节点，2*i+1存储右节点。
如下图：
那么什么时候用链式，什么时候用顺序存储？
我们看下这种二叉树下的顺序存储：
我们发现6这个下标其实没数据，那么就会存在内存浪费的问题，我们发现之前提到的满二叉树或者完全二叉树的结构下就不存在这个问题，因此完全二叉树完全可以用顺序存储代替链式存储，减少内存的使用（链式存储需要额外的左右指针）。
关于二叉树的遍历方式有：前序遍历、中序遍历、后序遍历。
我总结了一个口诀：前序就是根左右，中序就是左根右，后序就是左右根。
根据口诀我们写一下前面满二叉树的遍历结果：
前序：1、2、4、5、3、6、7
中序：4、2、5、1、6、3、7
后序：4、5、2、6、7、3、1
仔细观察你会发现一个规律：不管哪种遍历其实都是一个递归的过程，也是我总结的口诀适用于每个节点。
除了前中后序遍历还有一种遍历比较常见：按层遍历，遍历结果：1、2、3、4、5、6、7
这种遍历可以借助队列来实现，节点创建的同时入队，遍历时按照先进先出原则，便可得到按层遍历的结果。
二叉查找树
顾名思义，这个特殊的二叉树是为了快速查找而生，当然这种树插入和删除也很高效。
二叉查找树的特点：左节点的值节点的值右节点的值。
关于查找，这里其实用到了二分查找的思想，从根节点开始查找，会不断地往某个分叉倾斜。
关于插入，先借助查找找到数据需要插入的位置进行插入。
关于删除，删除比较复杂，需要考虑被删除节点的子节点情况，如果节点没有子节点，只需要把节点的父节点对应的指针指向null，如果节点只有左或者右节点，比较过后，将父节点的左右指针指向节点的子节点，如果节点左右节点都有，需要找到这个节点的右子树中的最小节点进行替换，再删除掉这个最小节点，因为最小节点肯定没有左子节点。
二叉查找树还可以支持快速查找到最大和最小的节点，还有一个特点就是根据中序遍历得到的结果就是排序好的。
关于二叉查找树的时间复杂度，最差的情况就是这颗二叉查找树，每个节点只有左节点或者只有右节点，O(n)的复杂度，显然这种极度不平衡的二叉树不符合二叉查找树的初衷。二叉查找树的初衷应该是完全二叉树或者满二叉树这种样子，这个时间复杂度取决于树的高度，那么最终其实就是计算n个节点的完全二叉树的高度，公式推导的过程就省略了，最终结果就是O(logn),这也符合我们的心理预期，因为是借助于二分查找的思想。
二叉查找树和散列表的对比
二叉查找树支持快速插入、删除和查找，同样散列表也支持这些，那么有什么区别？
二叉查找树：平衡二叉查找树性能稳定，中序遍历能够得到排序好的数据，
散列表：哈希冲突导致查找不一定是理论上的O(1)，需要考虑散列函数的设计、哈希冲突解决方案、扩容、缩容等问题
红黑树
前面我们提到了只有平衡二叉查找树的性能才是稳定的，那么什么是平衡二叉查找树？
平衡二叉树的特点：二叉树中任意一个节点的左右子树的高度相差不能大于1。这只是严格意义上的定义，并非一层不变，关键在于理解平衡二字，平衡的意义在于不要出现时间复杂度退化的问题，感性上就是这颗树要茂盛。
很显然我们之前说的完全二叉树、满二叉树都属于平衡二叉查找树，但是根据定义非完全二叉树也可能是平衡二叉查找树。
红黑树其实就是平衡二叉查找树中的一种，而且还是自平衡的。
顾名思义，红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：
1、根节点是黑色的；
2、每个叶子节点都是黑色的空节点，也就是说，叶子节点不存储数据；
3、任何同一路径的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
4、每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；
红黑树通过左旋、右旋和变色来保持树的平衡，先变色后自旋。
变色很好理解，就是红黑互变
关于左旋和右旋，如图：
关于红黑树的查找：红黑树首先是二叉查找树，所以查找根二叉查找树一样，从根节点遍历进行比较，利用二分查找的思想。
关于红黑树的插入和删除：因为插入和删除操作会破坏红黑树的平衡，所以需要通过左旋、右旋和变色的操作来保持红黑树的平衡，因此插入和删除操作相对来说也比较复杂。插入和删除操作有一定的规则，而且还有一堆不同场景下的公式，就跟魔方一样，有着对应的复原公式，日常开发中基本上不会碰到让你写一个平衡二叉查找树的需求，因此本篇也无需长篇讨论各种场景下的平衡公式，对于作者来说只需一个大概的理解即可。
下一篇讲B树和B+树。
mbond第22篇
