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
Tree-00-概览
目录
排序
二分查找法
Tree
二叉查找树
AVL Tree
红黑树
B Tree
B+ Tree
Tree-00-概览
Tree-01-二叉树 Binary Tree
Tree-02-java 实现 BST 二叉查询树详解
Tree-03-图解 AVL 自平衡二叉查找树及 java 实现
Tree-04-图解红黑树 Red Black Tree 及 java...
2020-10-17 08:15:55 |
Data-Struct
操作系统 动态内存管理 OS
动态内存管理
在计算机中,操作系统负责管理整个内存空间,主要概括为两个方面:内存的分配与回收。
本章中会详细介绍计算机中用于管理存储空间的方法,以及如何对产生的内存碎片进行处理。
数据结构之动态内存管理机制
通过前面的学习,介绍很多具体的数据结构的存储以及遍历的方式,过程中只是很表面地介绍了数据的存储,而没有涉及到更底层的有关的存储空间的分配与回收,从本节开始将做更深入地介绍。
在...
2020-10-17 08:15:55 |
OS