树结构（1）概述

大家好，欢迎来到IT知识分享网。

序言

为什么需要树这种数据结构？

树是一种非常实用的数据结构，最常用的就是数据库的索引，用于在海量数据查找目标值。

举个例子，如果你的表有1亿的数据。如果使用链表来存储，那么你最坏情况下需要遍历1亿次才能找到目标值。

但如果你使用红黑树来查找，那你最坏情况下的时间复杂度为 O(logN），即最坏只需要27次就可以找到。

27次查找与1亿次的查找，这中间相差了300万倍，由此可见树结构带来的效率提升之巨大！

那我们应该如何去学习树这种数据结构呢？

其实树这种数据结构也是有其知识体系的，每一种树结构的诞生都有其原因及实际场景。

我们需要找到这种场景，梳理出一条主线，将这些知识点串起来，形成一个知识体系。 例如我们所知道的树结构有：

• 树
• 二叉树
• 二叉查找树
• 二叉平衡树
• AVL树
• 红黑树
• B-树
• B+树
• 树堆
• 2-3树
• 伸展树
• Trie树
• 字母树
• 哈夫曼树

数组，查找很快，但是增删慢。

链表，插入和删除很快，但是查询速度慢。

我们希望有一种数据结构能同时具备数组查找快的优点以及链表插入和删除快的优点，于是树诞生了。

二叉树 

二叉树每个节点的子节点不允许超过两个。通过将子节点的个数限定为2，可以写出高效的程序在树中插入、查找和删除数据。

二叉树是递归定义的。

二叉查找树

二叉查找树是一种特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点中。

平衡二叉树（AVL树）

给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST), 并分析问题所在.

左边BST 存在的问题分析: 左子树全部为空，从形式上看，更像一个单链表.

插入速度没有影响

查询速度明显降低(因为需要依次比较), 不能发挥BST的优势，因为每次还需要比较左子树，其查询速度比单链表还慢

解决方案-平衡二叉树(AVL)

2-3树

我们回忆一下AVL树，它在插入和删除节点时，总要保证任意节点左右子树的高度差不超过1。正是因为有这样的限制，插入一个节点和删除一个节点都有可能调整多个节点的不平衡状态。频繁的左旋转和右旋转操作一定会影响整个AVL树的性能，除非是平衡与不平衡变化很少的情况下，否则AVL树所带来的搜索性能提升不足以弥补平衡树所带来的性能损耗。

那有没有绝对平衡的一种树呢？没有高度差也不会有平衡因子，没有平衡因子就不会调整旋转操作。2-3树正是一种绝对平衡的树，任意节点到它所有的叶子节点的深度都是相等的。

2-3树的数字代表一个节点有2到3个子树。它也满足二分搜索树的基本性质，但它不属于二分搜索树。

2-3-4树

从二分搜索树，到AVL树，再到2-3树，再到基于2-3树的红黑树，都可以发现这些树都跟二叉查找树很像啊。嘿嘿！二分搜索树就是二叉查找树；AVL树也是一颗二分搜索树，只多了高度差的限制；2-3树虽满足二分搜索树的性质，但不是一颗二分搜索树，2-3树由2-节点和3-节点组成的，满足了完美平衡性；基于2-3树的红黑树就是希望不要有3-节点，将3-节点转换成二叉，两个元素之间由红链接相连，并约定谁是子节点谁是红的

B树

文件系统和数据库系统一般都采用树（特别是B树）的数据结构数据，主要为排序和检索的效率。二叉树是一种最基本最典型的排序树，用于教学和研究树的特性，本身很少在实际中进行应用，因为缺点太明显了（看看教科书怎么说的）。就像冒泡排序一样，虽然因为效率问题并不实用，单不失一种教学例子的好手段。

B树是一种非常优雅的数据结构。是关系数据库和文件系统的核心算法。对于B树的了解会使得你对于数据库的学习更加系统和容易。

B树是对二叉查找树的改进。它的设计思想是，将相关数据尽量集中在一起，以便一次读取多个数据，减少硬盘操作次数。

B树的特点也有三个。

1. 一个节点可以容纳多个值。比如上图中，最多的一个节点容纳了4个值。
2. 除非数据已经填满，否则不会增加新的层。也就是说，B树追求”层”越少越好。
3. 子节点中的值，与父节点中的值，有严格的大小对应关系。一般来说，如果父节点有a个值，那么就有a+1个子节点。比如上图中，父节点有两个值（7和16），就对应三个子节点，第一个子节点都是小于7的值，最后一个子节点都是大于16的值，中间的子节点就是7和16之间的值。

这种数据结构，非常有利于减少读取硬盘的次数。假定一个节点可以容纳100个值，那么3层的B树可以容纳100万个数据，如果换成二叉查找树，则需要20层！

假定操作系统一次读取一个节点，并且根节点保留在内存中，那么B树在100万个数据中查找目标值，只需要读取两次硬盘。

索引

数据库以B树格式储存，只解决了按照”主键”查找数据的问题。如果想查找其他字段，就需要建立索引（index）。

所谓索引，就是以某个字段为关键字的B树文件。假定有一张”雇员表”，包含了员工号（主键）和姓名两个字段。可以对姓名建立索引文件，该文件以B树格式对姓名进行储存，每个姓名后面是其在数据库中的位置（即第几条记录）。

查找姓名的时候，先从索引中找到对应第几条记录，然后再从表格中读取。

这种索引查找方法，叫做”索引顺序存取方法”（Indexed Sequential Access Method），缩写为ISAM。它已经有多种实现（比如C-ISAM库和D-ISAM库），只要使用这些代码库，就能自己写一个最简单的数据库。

B+

为什么文件存储要选用B+树这样的数据结构？

因为要降低搜索一个文件的IO的次数。

比如一个1000度的B树，磁盘上面有10亿个文件的话，B树只需要4次就好了。其他的数据结构做不到。

磁盘很慢，当涉及到磁盘的输入输出的时候，CPU的时间就已经可以忽略不计了，数据结构的设计要集中考虑到尽可能降低IO的次数，所以B树应运而生。

MySQL数据库的索引就是基于B+树。

B-

红黑树

虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logn)，不过却不是最佳的。

因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。

显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树。

红黑树具有如下特点：

1、具有二叉查找树的特点。

2、根节点是黑色的；

3、每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存数据。

4、任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的。

5、每个节点，从该节点到达其可达的叶子节点是所有路径，都包含相同数目的黑色节点。

正是由于红黑树的这种特点，使得它能够在最坏情况下，也能在 O(logn) 的时间复杂度查找到某个节点。

不过，与平衡树不同的是，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整，这也是我们为什么大多数情况下使用红黑树的原因。

不过，如果你要说，单单在查找方面的效率的话，平衡树比红黑树快。

所以，我们也可以说，红黑树是一种不大严格的平衡树。也可以说是一个折中发方案。

而关于红黑树的应用，一个非常经典的就是JDK1.8的HashMap中，当链表长度超过8时，就会由链表变成红黑树 

总结

有了二叉查找树、平衡树（AVL）为啥还需要红黑树？

平衡树是为了解决二叉查找树退化为链表的情况，而红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况。

资料

红黑树其实很简单

从根源上探究红黑树的本质

二叉树与多叉树

了解红黑树的起源，理解红黑树的本质

二叉查找树、平衡树（AVL）为啥还需要红黑树？

红黑树这个数据结构，让你又爱又恨？看了这篇，妥妥的征服它

腾讯面试题：有了二叉查找树、平衡树为啥还需要红黑树？

动画 | 什么是红黑树？（与2-3-4树等价）

硬核数据结构，让你从B树理解到B+树

https://www.cnblogs.com/chanshuyi/tag/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/