• Tree-06-多路查找树 B+ 树 及 java 实现
  B+ 树的概念 B+ 树是应文件系统所需而产生的一种B Tree的变形树。 描述 B Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。 与B Tree相比，B+Tree有以下不同点： 每个节点的指针上限为2d而不是2d+1。 内节点不存储data，只存储key；叶子节点不存储指针。 图3是一个简单的B+Tree示意。 由...
  2020-10-17 08:15:55 | Data-Struct
• Tree-05-多路查找树 BTree 及 java 实现
  BTree 历史 在1970年，Bayer＆McCreight发表的论文《ORGANIZATION AND MAINTENANCE OF LARGE ORDERED INDICES》（大型有序索引的组织和维护）中提出了一种新的数据结构来维护大型索引，这种数据结构在论文中称为B Tree。 B树的定义 h：代表树的高度，k 是个自然数，一个B树要么是空的，要么满足以下条件： ...
  2020-10-17 08:15:55 | Data-Struct
• Tree-06- B 树之 2-3 Tree
  2-3 树 2–3树是一种树型数据结构，内部节点（存在子节点的节点）要么有2个孩子和1个数据元素，要么有3个孩子和2个数据元素，叶子节点没有孩子，并且有1个或2个数据元素。 2–3树由约翰·霍普克洛夫特于1970年发明。 2–3树和AA树是等距同构的，意味着它们是同一种数据结构。 换句话说，对于每个2–3树，都至少有1个AA树和它的元素排列是相同的。 2–3树是平衡树，意味着右边，...
  2020-10-17 08:15:55 | Data-Struct
• Tree-05-伸展树 Splay Tree 及 java 实现
  伸展树 伸展树（英语：Splay Tree）是一种能够自我平衡的二叉查找树，它能在均摊 O(log n) 的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。 它是由丹尼尔·斯立特（Daniel Sleator）和罗伯特·塔扬在1985年发明的。 核心思想 考虑到局部性原理（刚被访问的内容下次可能仍会被访问，查找次数多的内容可能下一次会被访问），为了使整个查找时间更小...
  2020-10-17 08:15:55 | Data-Struct
• Tree-04-图解红黑树 Red Black Tree 及 java 实现
  Red Black Tree 红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。 它是在1972年由鲁道夫·贝尔发明的，他称之为”对称二叉B树”，它现代的名字是在Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。 它是复杂的，但它的操作有着良好的最坏情况运行时间，...
  2020-10-17 08:15:55 | Data-Struct
• Tree-03-图解 AVL 自平衡二叉查找树及 java 实现
  AVL树 AVL树是根据它的发明者G.M. Adelson-Velsky和E.M. Landis命名的。 它是最先发明的自平衡二叉查找树（Self-balancing binary search tree），也被称为高度平衡树。 相比于”二叉查找树”，它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。 例子 AVL 平衡树 5 2 7 1 3 6 9 ...
  2020-10-17 08:15:55 | Data-Struct
• Tree-02-java 实现 BST 二叉查询树详解
  回顾 前面我们学习了 java 如何实现 binary search 二分查找法？。 那么，有没有一种数据结构，可以让我们更好的实现二分查找呢？ 有的，那就是我们今天的二叉查询树。 让我们从二叉树开始，一起完成这次查询的学习之旅吧。 二叉树（Binary Tree） 概念 顾名思义，就是一个节点分出两个节点，称其为左右子节点；每个子节点又可以分出两个子节点，这样递归分叉，其形状...
  2020-10-17 08:15:55 | Data-Struct
• Tree-01-二叉树 Binary Tree
  二叉树（Binary Tree） 顾名思义，就是一个节点分出两个节点，称其为左右子节点；每个子节点又可以分出两个子节点，这样递归分叉，其形状很像一颗倒着的树。 二叉树限制了每个节点最多有两个子节点，没有子节点的节点称为叶子。 二叉树引导出很多名词概念，这里先不做系统介绍，遇到时再结合例子一一说明。 如下一个二叉树： /* A simple binary tree * ...
  2020-10-17 08:15:55 | Data-Struct