二叉查找树

二叉查找树英语Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sorted binary tree)。二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合multiset关联数组等。

二叉查找树是指一棵空树或者具有下列性质的二叉树

  1. 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  2. 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  3. 任意节点的左、右子树也分别为二叉查找树。
  4. 没有键值相等的节点(英语:no duplicate nodes)。

注:维基百科和百度百科上性质【1】和【2】不同,描述中的一个性质会存在键值相等的情况,考虑到性质【4】,是不应该存在这个相等情况的。

注:以上定义摘自维基百科(微幅修改)。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低,等于树高,期望为O(log n),最坏为O(n)。

二叉查找树

两个高度相同的二叉查找树

上面的两个二叉查找树树高是一样的,但是查找是速度是相同的。

下面介绍二叉查找树的一些操作:

继续阅读

linux内核同步方法-原子操作

转自:edsionte's TechBlog

原子操作

原子操作用于执行轻量级、仅执行一次的操作,比如修改计数器,某些条件下的增加值或设置位等。原子操作指的是指令以原子的方式执行。之所以用原子来修饰这种操作方式是因为它们均不可再分。也就是说,原子操作要么一次性执行完毕,要么就不执行,这些操作的执行过程是不可被打断的。原子操作的具体实现取决于体系架构,以下代码如无特别声明,均来自linux/arch/x86/include/asm/atomic.h中

内核中提供了两组原子操作的接口:原子整形操作和原子位操作。前者是一组对整形数据的操作,后者则是针对单独的位操作。通过上面的叙述我们可以知道,这写操作接口完成的动作都是原子的。

继续阅读

堆排序

上次写了个快排的文章,果不其然被大家鄙视了。大概平时是一个写脚本的,这东西也不会了,大学时代还能帮别人替考c语言,现在连c都不写了。

回归正题,这里使用二叉堆,二叉堆是一个近似的完全二叉树,在很多地方都会用到这个结构。

通常使用数组来表示一个堆:假设数组第一个元素为根节点,那么它的左孩子节点就是第二个元素,右孩子节点为第三个元素。以此类推,假设一个节点是数组的第n个元素,它的左孩子节点就是第2n个元素,右孩子节点就是2n+1,可以使用floor(n/2)来获取其父节点。

二叉堆分为最大堆(MAX-HEAP,大顶堆)和最小堆(MIN-HEAP,小顶堆),最大堆就是父节点的值大于或等于子节点值的堆,所以根节点应该是最大的节点,最小堆反之。这里使用了最大堆。

继续阅读