一、树是什么?
有根有枝叶便是树!根只有一个,枝叶可以有,也可以没有,可以有一个,也可以有很多。
就像这样:
嗯,应该是这样:
二、一些概念
1、高度
树有多高,嗯,我一米八三!
树的高度怎么算?
高度是啥,就是从下往上到最顶端,从叶节点到根节点。
从每个叶节点开始,一个节点一个节点往上数,数到根节点,最长的那个数就是数的高度。叶节点起始为0.
上面这个树的高度是4。
2、深度
深度,顾名思义,就是从上往下到最低端,从根节点到叶节点。
从根开始,一个节点一个节点往下数,数到每个叶子节点,最长的那个数就是数的深度。根节点的起始为0.
上面这个树的深度是4。
对比上面的高度,看到了哈,数值是一样的,
3、层
一层是什么呢。就是横向的同一高度的所有节点凑一块儿就是一层。
像下面一条线连接了第二层所有的节点:
三、二叉树的遍历
二叉树是什么?
二叉树就是每个节点最多有两个分叉子节点。
遍历是什么意思?
遍历就是一个树的所有节点都点一遍,那么既然要点一遍,总归要遵循一个特定的顺序,不然,乱来的话总会可能漏一个,或者多一个。
像下面这棵树:
1、前序遍历
顺序:中左右
中 6 -> 左中 5 -> 左 2 -> 右 3 -> 右中 7 -> 右 8
结果就是:6、5、2、3、7、8。
2、中序遍历
顺序:左中右
左 2 -> 中 5 -> 右 3 -> 中 6 -> 右中 7 -> 右 8
结果就是: 2、5、3、6、7、8。
3、后序遍历
顺序:左右中
左 2 -> 右 3 -> 中左 5 -> 右 8 -> 中右 7 -> 中 6
结果就是:2、3、5、8、7、6.
这个顺序,其实很容易混乱。想要记得牢,只需要一点:
【前、中、后】,前为左,右为后,哪个顺序遍历,那么哪个节点就会顺序居中,其它的节点,靠左的居前。
节点的巡查是从根节点出发,从上到下,从左至右巡查,每个节点及其子点巡查完毕后,再跳出到其它节点。
4、附加:层序遍历
层序遍历很简单就是从上到下,一层一层的收拢节点。
第一层 6 -> 第二层 5、7 -> 第三层 2、3、8
结果就是:6、5、7、2、3、8.
四、树能干什么?
树能盖房子!
没错,树通常用来搭建存储数据的房子。
数据存储是对数据的持久化保存,针对数据的操作包括读和写。不过,无论是读还是写,都离不开对数据的检索操作。
1、B树
之前文章介绍过B树及在数据库存储方面的应用:
你好,我是B树
MySQL InnoDB 是怎么使用 B+ 树存数据的?
B 树,即balance tree。其结构及节点数据分布遵循特定的规则。
B 树的算法运行时间通常由它所执行的【磁盘读写操作次数】决定,所有一般会一次尽可能的读写更多的信息。一个B树节点通常和一个完整的磁盘页大小相同,所以磁盘页的大小限制了一个B树节点所能包含孩子节点的个数。
B 树每个节点会包含多少个分支,称之为分支因子。分支因子越大,B 的高度越低,查找关键字所需的磁盘存取次数越少,查询时间越短。这也是为什么会推崇使用B树结构来作为数据底层存储。
2、二叉搜索树
二叉搜索树是以一棵二叉树来组织数据存储,每个节点除了包含数据本身外,还包括指向左节点、右节点及父节点的指针,即key、left、right、p。其中存储数据需满足左中右非降序存储,即left.key <= key <= right.key。
左中右,是不是很熟悉,就是我们上面讲到过的【中序遍历】顺序。【中序遍历】输出的话,整个数列会是非降序排序数列。
搜索树结构通常支持包括查找,最大值,最小值,插入,删除等操作。嗯,这些操作是不是又很熟悉,总之就是一个【日常操作】。
二叉搜索树上的操作时间和它的高度成正比,对于n节点二叉树,通常最坏运行时间为O(lgn)(为什么是O(lgn)呢?这个需要推导,先记住就行了),这个就是树元素随机分步的情况下的结果。极端情况下,一条链从根到叶的话,时间固定就是O(n)了。就像下面这个棵树:
3、红黑树
红黑树也是一个二叉搜索树。那为什么会需要这么一棵树呢?
就是为了避免上面哪种极端或者接近极端情况的出现。它可以【保证最坏的情况下操作时间复杂度为O(lgn)】。
对的,是保证!那怎么保证呢?当然是通过维持红黑树本身的结构特点来实现。
我们上面及到过二叉搜索树节点包含的数据,红黑树会在其基础上增加一个存储位来表示节点的颜色(红或者黑)。通过【对任何一条从根到叶子节点的简单路径上的各个节点颜色进行约束】来确保【没有一路径会比其它路径长2倍】。
红黑树的特点:
-
a)【节点要么红,要么黑】
-
b)【根节点是黑的】
-
c)【叶节点是黑的】
-
d)【如果一个节点是红色的,那么它的子节点是黑色的】
-
e)【对任何一个节点,从该节点到其所有后代叶节点的简单路径上的黑节点数据是相同的】
这里有个点需要强调一下,红黑树里所说的叶子节点指的是【外部节点】,也就是不包含 key 的节点。
黑高:从某个节点到达其叶节点的【任何一个(参考e】简单路径上的黑色节点个数称之为黑高。红黑树的黑高即为其根节点的黑高。
一颗有 n 个内部节点的红黑树的高度至多为 2lg(n+1),也即我们前面说的能够保证最坏的情况下操作时间复杂度为O(lgn)。
红黑树有哪些应用呢?
最常见的就是 HashMap了,用于解决存储元素哈希冲突,当链表元素个数超过8时,即转为红黑树。