数据结构系列 - 红黑树

一、红黑树介绍

红黑树由Rudolf Bayer于1972年发明,当时被称为平衡二叉B树(symmetric binary B-trees),1978年被Leonidas J. Guibas 和 Robert Sedgewick改成一个比较摩登的名字:红黑树。

 

二、红黑树与AVL树比较

红黑树AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。自从红黑树出来后,AVL树就被放到了博物馆里,据说是红黑树有更好的效率,更高的统计性能。
红黑树和AVL树的区别:红黑树使用颜色来标识结点的高度,它所追求的是局部平衡而[......]

查看全文

数据结构系列 - 图的遍历

与树类似,遍历也是图的一种重要的操作,图的遍历是访问图中每个顶点仅被访问一次的操作。图的遍历方式主要有两种:深度优先遍历和广度优先遍历。本节的主要学习内容包括图的深度优先遍历、图的广度优先遍历。

 

1. 图的深度优先遍历

 

深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则已w为心的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点为新的源点重复上述过程,直至图中所有的顶点均已被访问为止。[......]

查看全文

数据结构系列 - 图

1. 前言

图是一种非线性数据结构,是一种更为复杂的数据结构,在图中,数据元素之间时多对多的关系,即一个数据元素对应多个直接前驱和多个直接后继元素。图的应用领域十分广泛,如化学分析,工程设计、遗传学、人工智能等。

2. 图的定义和相关概念

图是一种数据元素间为多对多关系的数据结构,加上一组基本操作构成的抽象数据类型。

数据对象V :V是具有相同特性的数据元素的集合,称为顶点集。

数据关系R:

R={VR}

VR={<v,w>|v,w(-V且P(v,w),<v,w>表示从v到w的弧,谓词P(v,w)定义了弧<v,w>的意义[......]

查看全文

数据结构系列 - 哈夫曼树

1.树的路径长度
     树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中,完全二叉树的路径长度最短。

2.树的带权路径长度(Weighted Path Length of Tree,简记为WPL)
结点的权:在一些应用中,赋予树中结点的一个有某种意义的实数。
结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。
树的带权路径长度(Weighted Path Length of Tree):定义为树中所有叶结点的带权路径长度之和,通常记为:

其中:

n表示叶子结点的数目
wi和li分别表示叶结点ki的权值和根到结点ki[......]

查看全文

数据结构系列 - 树的转换

1. 树的存储结构

    通常,树的存储结构有三种,双亲表示法、孩子表示法和孩子兄弟表示法。

(1)双亲表示法

双亲表示法是利用一组连续的存储单元存储树的每个结点,并利用一个指示器表示结点的双亲结点在树中的位置。

树的双亲表示法存储表示描述如下:

 

C代码  收藏代码
  1. #define MaxSize 200
  2. typedef struct PNode        /* 双亲表示法的结点定义 */
  3. {
  4.     DataType data;
  5.     int parent;                    /*[......]

    查看全文

1 2 3 4 10