Tree-00-概览

排序

二分查找法

Tree

二叉查找树

AVL Tree

红黑树

B Tree

B+ Tree

Tree-00-概览

Tree-01-二叉树 Binary Tree

老马啸西风2020年10月17日大约 3 分钟

Tree-01-二叉树 Binary Tree

顾名思义，就是一个节点分出两个节点，称其为左右子节点；每个子节点又可以分出两个子节点，这样递归分叉，其形状很像一颗倒着的树。

二叉树限制了每个节点最多有两个子节点，没有子节点的节点称为叶子。

二叉树引导出很多名词概念，这里先不做系统介绍，遇到时再结合例子一一说明。

如下一个二叉树：

/*   A simple binary tree
 *        A ---------> A is root node
 *       / \
 *      /   \
 *     B     C
 *    /     / \
 *   /     /   \
 *   D     E    F ---> leaves: D, E, F
 *
 *       (1)      ---> Height: 3
 */

老马啸西风2020年10月17日大约 43 分钟

Tree-02-java 实现 BST 二叉查询树详解

前面我们学习了 java 如何实现 binary search 二分查找法？。

那么，有没有一种数据结构，可以让我们更好的实现二分查找呢？

有的，那就是我们今天的二叉查询树。

让我们从二叉树开始，一起完成这次查询的学习之旅吧。

二叉树（Binary Tree）

概念

顾名思义，就是一个节点分出两个节点，称其为左右子节点；每个子节点又可以分出两个子节点，这样递归分叉，其形状很像一颗倒着的树。

老马啸西风2020年10月17日大约 23 分钟

Tree-03-图解 AVL 自平衡二叉查找树及 java 实现

AVL树

AVL树是根据它的发明者G.M. Adelson-Velsky和E.M. Landis命名的。

它是最先发明的自平衡二叉查找树（Self-balancing binary search tree），也被称为高度平衡树。

老马啸西风2020年10月17日大约 8 分钟

Tree-04-图解红黑树 Red Black Tree 及 java 实现

红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。

它是在1972年由鲁道夫·贝尔发明的，他称之为"对称二叉B树"，它现代的名字是在Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。

它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在 O(lg(n)) 时间内做查找，插入和删除，这里的 n 是树中元素的数目。

用途和好处

红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。

老马啸西风2020年10月17日大约 32 分钟

Tree-05-伸展树 Splay Tree 及 java 实现

伸展树（英语：Splay Tree）是一种能够自我平衡的二叉查找树，它能在均摊 O(log n) 的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。

它是由丹尼尔·斯立特（Daniel Sleator）和罗伯特·塔扬在1985年发明的。

核心思想

考虑到局部性原理（刚被访问的内容下次可能仍会被访问，查找次数多的内容可能下一次会被访问），为了使整个查找时间更小，被查频率高的那些节点应当经常处于靠近树根的位置。

ps: 这个思想实际上非常的简单，也非常的实用。我们以前实现的 LFU 的思想是类似的。

老马啸西风2020年10月17日大约 24 分钟

Tree-06- B 树之 2-3 Tree

2–3树是一种树型数据结构，内部节点（存在子节点的节点）要么有2个孩子和1个数据元素，要么有3个孩子和2个数据元素，叶子节点没有孩子，并且有1个或2个数据元素。

2–3树由约翰·霍普克洛夫特于1970年发明。

2–3树和AA树是等距同构的，意味着它们是同一种数据结构。

换句话说，对于每个2–3树，都至少有1个AA树和它的元素排列是相同的。

2–3树是平衡树，意味着右边，左边，中间的子树的元素数量都是相同或接近的。

定义

（1）2-3 树要么为空要么具有以下性质：

老马啸西风2020年10月17日大约 7 分钟

Tree-08-多路查找树 BTree 及 java 实现

在1970年，Bayer＆McCreight发表的论文《ORGANIZATION AND MAINTENANCE OF LARGE ORDERED INDICES》（大型有序索引的组织和维护）中提出了一种新的数据结构来维护大型索引，这种数据结构在论文中称为B Tree。

B树的定义

h：代表树的高度，k 是个自然数，一个B树要么是空的，要么满足以下条件：

所有叶子节点到根节点的路径长度相同，即具有相同的高度；（树是平衡的）
每个非叶子和根节点（即内部节点）至少有 k+1 个孩子节点，根至少有 2 个孩子；（这是关键的部分，因为节点都是分裂而来的，而每次分裂得到的节点至少有 k 个元素，也就有 k+1 个孩子；但根节点在分裂后可能只有一个元素，因为不需要向上融合，中间元素作为新的根节点，因此最少有两个孩子。而叶子节点没有孩子。）
每个节点最多有 2k+1 个孩子节点。（规定了节点的最大容量）
每个节点内的键都是递增的