树的介绍

树是一种非线性的数据结构，将它命名为“树”是因为它看起来像一颗倒挂的树，根朝上，页朝下。

树的基本术语

A 节点就是 B 节点的父节点，B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。我们把没有父节点的节点叫作根节点，也就是图中的节点 E。我们把没有子节点的节点叫作叶子节点或者叶节点，比如图中的 G、H、I、J、K、L 都是叶子节点。

关于“树”，还有三个比较相似的概念：高度（Height）、深度（Depth）、层（Level）。它们的定义是这样的：

二叉树

二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。

其中，编号 2 的二叉树中，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。

编号 3 的二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。

储存方式

一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。

我们先来看比较简单、直观的链式存储法。从图中你应该可以很清楚地看到，每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式我们比较常用。大部分二叉树代码都是通过这种结构来实现的。

我们再来看，基于数组的顺序存储法。我们把根节点存储在下标 i = 1 的位置，那左子节点存储在下标 2 i = 2 的位置，右子节点存储在 2 i + 1 = 3 的位置。以此类推，B 节点的左子节点存储在 2 i = 2 2 = 4 的位置，右子节点存储在 2 i + 1 = 2 2 + 1 = 5 的位置。

不过，我刚刚举的例子是一棵完全二叉树，所以仅仅“浪费”了一个下标为 0 的存储位置。如果是非完全二叉树，其实会浪费比较多的数组存储空间。

所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因。

遍历二叉树

深度优先遍历的方法有三种，前序遍历、中序遍历和后序遍历。

• 前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
• 中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
• 后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

广度优先遍历：这种遍历算法将逐层访问每层的节点，先访问根（第一层）节点，然后访问第二层的节点…..一次类推。因此，广度优先遍历方法又被称为按层遍历。

二叉查找树

二叉查找树是一种特殊结构的二叉树，通过它可以非常方便地对树中的所有节点进行排序和检索

二叉查找树要么是一颗空二叉树，要么是具有下列性质的二叉树

• 若它的左子树不空，则左子树上所有的节点的值均小于它的根节点的值
• 若它的右子树不空，则右子树上所有的节点均大于它的根节点的值
• 它的左右子树分别为排序二叉树。

查找操作：

我们看如何在二叉查找树中查找一个节点。我们先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。

这时我们会发现如果左子树和右子树高度差距过大，其实很容易产生极端情况。

如果是上图第一种，效率会是最低，最理想的情况是第三种，完全二叉树。

显然，极度不平衡的二叉查找树，它的查找性能肯定不能满足我们的需求。我们需要构建一种不管怎么删除、插入数据，在任何时候，都能保持任意节点左右子树都比较平衡的二叉查找树

平衡二叉查找树

平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。从这个定义来看，上一节我们讲的完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。

AVL就是一种高度平衡二叉树，但它为了达到自平衡的效果，增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。这样使用 AVL 树的代价就有点高了。

所以很多平衡二叉查找树其实并没有严格符合上面的定义（树中任意一个节点的左右子树的高度相差不能大于 1），比如我们下面要讲的红黑树，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。

发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。

所以，平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。

红黑树

介绍

红黑树的应用非常广泛，常见的函数库，如 C++中的 map，multimap,以及 Java 中的 TreeMap，TreeSet， Java8 中的 HashMap 的实现也采用了红黑树。

红黑树从本质上来说就是一颗二叉查找树，但是在二叉树的基础上增加了着色相关的性质，使得红黑树可以保证相对平衡，从而保证红黑树的增删改查的时间复杂度最坏也能达到 O(log N)。

顾名思义，红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：

• 根节点是黑色的；
• 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
• 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
• 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；。

上图是一棵典型的红黑树，红黑树的 5 条特性确保了从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，使得整棵树大致上是平衡的。树上的增删改查操作的最坏情况时间都与树的高度成正比，所以红黑树在最坏情况下也是高效的。

在红黑树中一般用黑的 NIL 节点表示叶节点，不包含值，只是标志该分支结束，有时候绘图中会直接省略。

旋转

当在含 n 个关键字的红黑树上进行 insert 和 delete 操作时，修改后的树可能不满足上面给出的 5 个红黑树的基本特性，所以需要改变树中的某些节点的颜色以及指针结构。 这些指针结构的修改是通过旋转完成的，旋转分为左旋和右旋:

参考文档

疯狂 java 笔记之树和二叉树

图解红黑树