MENU

凸包问题

首先介绍下什么是凸包?如下图:

在一个二维坐标系中,有若干点杂乱排列着,将最外层的点连接起来构成的凸多边型,它能包含给定的所有的点,这个多边形就是凸包。

阅读全文

向量积与线段相交问题

一:什么是向量积?

向量积,也称(向量)叉积,(向量)叉乘,外积,是一种在向量空间中对向量进行的二元运算。常见于物理学力学、电磁学、光学和计算机图形学等理工学科中,是一种很重要的概念。

阅读全文

位运算总结

位运算,相比普通的代码最大的优点就是其带来的高效性,也因此可以常在底层源码中看见它们的踪影。

本文就位运算常见的操作作一个总结,若您另有关于位运算巧妙的运用可以于底部留言区留言。

首先还是先来回顾下位操作的基础知识。(除非特别说明,否则以下都以2进制为例)

阅读全文

B-树(1):定义及其代码实现

系列文章目录

B-树(1):定义及其代码实现
B-树(2):应用及其拓展

一:背景

B-树(或者B树,英语:B-Tree)是一种自平衡的树,这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作,都在对数时间$O(logn)$内完成。与其它一般化的二叉查找树不同,它可以拥有多余2个子结点。

B-树为系统大块数据的读写操作做了优化,减少定位记录时所经历的中间过程,从而加快存取速度。这种数据结构可以用来描述外部存储,因此常被应用在数据库和文件系统的实现上。

一棵B-树具有如下性质:

阅读全文

跳跃表

一:背景

跳跃表(英文名:Skip List),于1990年William Pugh发明,是一个可以在有序元素中实现快速查询的数据结构,其插入,查找,删除操作的平均效率都为$O(logn)$。

跳跃表的整体性能可以和二叉查找树(AVL树,红黑树等)相媲美,其在RedisLevelDB中都有广泛的应用。

阅读全文

AVL树和红黑树的对比

前面已经分别介绍了两种平衡二叉树:AVL树红黑树,先让我们来简单回顾下。

AVL树,规定其任一结点下左右子树高度不超过1。

红黑树,规定其必须满足四个性质:

  1. 每个结点要么是红的,要么是黑的;

  2. 根结点是黑色的;

  3. 如果一个结点是红色的,则它的两个孩子都是黑色的;

  4. 对于任意一个结点,其到叶子结点的每条路径上都包含相同数目的黑色结点。

阅读全文

红黑树

一:背景

红黑树(英语:Red–Black Tree,简称RB-Tree)是一种平衡的二叉查找树,用途广泛。例如:

  • Java中的:java.util.TreeMap,java.util.TreeSet;

  • C++ STL中的:map,multimap,multiset。

它是在1972年由Rudolf Bayer发明的,他称之为"对称二叉B树",它现代的名字(即"红黑树")是Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。

红黑树的实现比较复杂,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的,它可以在$O(logn)$时间内做查找,插入和删除操作。

阅读全文