数据结构（一）--树_树边的集合怎么看

树的定义

什么是树 ：一棵树是一些节点的集合。这个集合可以是空集；若不是空集，则树由称作根的节点r以及0或多个非空的子树组成，这些子树中每一颗的根都被来自根r的一条有向的边所连接。也就是说，一棵树是N个节点和N-1条边的集合。

一些名字解释
儿子：节点的子树的根叫做该节点的儿子；
父亲：该节点就是儿子的父亲；
树叶：没有儿子的节点称作树叶；
兄弟：具有相同父亲的节点叫做兄弟；
深度：从节点n到根r的长度为深度，r的深度为0；
高度：从节点n到树叶的最长长度为高度，所有树叶的高度为0；一棵树的高度就是根的高度；

先、中、后序遍历
先、中、后指的是操作根节点的顺序，左节点先于右节点操作，所以先、中、后序遍历的执行顺序分别为：根-左-右、左-根-右、左-右-根。

二叉查找树

二叉树是在树的基础上限定了儿子的个数小于等于2而得到的。而对于二叉查找树，就是在二叉树的定义上在加一个限制：对于任意节点X，它的左子树的所有值都小于X，它的右子树的所有值都大于X。
二叉查找树的java实现

AVL树

为了防止二叉查找树退化为链表，我们需要再加一些限制：平衡
AVL(Adelson-Velskii和Landis)树带有平衡条件：对于任意节点，它的左子树和右子树的高度差最多为1（我们定义空树的高度为-1）。
平衡条件防止二叉树退化为链表，但是也给插入和删除增加了实现难度。以插入为例，根据不同的插入情况，可以分为四种类型：

1. 对a节点的左儿子的左子树插入 LL
2. 对a节点的左儿子的右子树插入 LR
3. 对a节点的右儿子的左子树插入 RL
4. 对a节点的右儿子的右子树插入 RR
   上述a节点表示第一个出现不平衡的节点，第一表示从树叶开始算（要不然肯定都是根节点）。
   对于1和4，插入的情况放生在两边，通过一次单旋转可以解决平衡问题；2和3发生在中间，需要双旋转（其实就是两次单旋转）来解决平衡问题。

单旋转

以RR为例，如下图
节点6为新插入的节点，插入后，2节点的左子树高度为1，右子树高度为3，不平衡。6插入的是2节点的右儿子的右子树，所以属于RR情况。对于RR情况，需要在a节点（例子中的2节点）和它的右儿子（4节点）之间进行一次左旋转，所谓左旋转就是：父节点旋转为右儿子的左儿子。在这个过程中，如果右儿子有左儿子，则该左儿子就是原父节点的新右儿子。

以图中例子总结左旋转过程：

1. 设置2节点的右儿子为4的左儿子3
2. 设置右儿子4的左儿子为原父节点2

需要注意的是，上述例子中6节点插入到了5节点的右儿子，这个不是成为RR情况原因，6节点插入到5节点的左儿子也是属于RR，请注意四种情况的定义，找到a节点，以它为出发点判断失衡情况。

LL的右旋转请大家自己尝试，有问题可以留言讨论

双旋转

现在大家已经明白左右旋转了，现在结合两个旋转来完成双旋转。以下图为例
如下图，节点5插入到了2节点的右儿子的左子树中，所以属于RL。我们需要从树叶到根进行先后两次单旋转，右旋转和左旋转。

需要注意的是，一：从树叶到根的顺序；二：旋转顺序，RL就是先右后左，LR就是先左后右。

java实现

伸展树

提出伸展树的背景：

1. 对于二叉查找树（不是AVL树），访问一个节点的时间复杂度为O(logN)，最坏情况是O(N)，如果经常出现最坏情况，比如一直访问同一个节点，此时耗费的时间会比较大
2. 一个节点被访问后，该节点和访问过程中路过的节点的访问可能性会增大。

在这样的背景下，伸展树的用途就是可以将被访问到的节点推到根节点，而且访问途中的节点深度不会很大（即访问时间也比较小）。

展开

因为我们的目的是要把目标X节点推到根部，所以需要沿着访问路径通过某些操作将X一步一步的推到根部。我们可能最先想到的就是使用旋转，每次让X和它的父节点旋转，这样到最后X就会出现到根部。但是这样的操作之后会造成沿途节点在一个比较深的位置。所以我们通过以下两种情况来分别处理。讨论之前先明确一点，目标X存在祖父节点（如果只有父节点就直接和父节点旋转）。

之子型

如图，类似于LR的情况（RL类似），我们就进行一次双旋转

一字型

如图情况，则按照图中规则操作。

java中树的应用

java中常见的比如TreeSet、TreeMap以及HashMap中链表过深转换的树形结构。这些树都属于红黑树，在后面写到红黑树的时候会详细解读这里。

以上~ . ~
感谢5.1还在学习的我们