文档章节

Redis研究-3.3数据结构之树与查找、排序等

会飞的杨先生
 会飞的杨先生
发布于 2015/08/26 22:35
字数 3408
阅读 1557
收藏 5
点赞 0
评论 0
1.树相关的内容
  1.1 Tree概念
      树是n(n>=0)个节点的有限集。n=0的时候,我们把它叫做空树。在任何一非空树中满足两个特点:(1) 有且只有一个叫做根的节点。(2)n>1时,其余节点可分为m(m>0)个 互不相交的有限集T1,T2,...其中每一个结合本身也是一棵树。
     上面的这概念用到了递归的定义。

    树的相关概念:
    节点的度:是指这个节点的子树的个数。
    树的度:是指树的节点中拥有最大多数量的节点的度。
   节点的关系:节点的子树的根叫做该节点的 孩子,相应的,该节点成为孩子的 双亲(父母同体)。同一个双亲的孩子之间叫做 兄弟,节点的祖先是从根节点到该节点所经历的分支上的所有的节点。以某节点为根的子树中的任一节点都是该节点的 子孙
    节点的层次:节点的层次从根开始定义,根为第一层,根的孩子为第二层,以此类推。双亲在同一层的互为堂兄弟。
    树的深度:树中节点的最大层次叫做树的深度或者高度。
我们用一颗树来说清楚上面的概念。
 
其中,节点D的度是3,因为他有3颗子树,整棵树的度是4,因为整棵树中所有的节点的最大的度是G,他有4颗子树。节点D、E叫做兄弟。
D、E、F是堂兄弟,而且树的深度为4.
1.2 树的结构和存储
   通过上面的描述,我们知道,一棵树是由节点来构成的,因此树节点是最基本的组成单位,那么,一棵树的节点有怎么表示或者说是怎么构成的呢?我们知道,一棵树的节点他不可能是从石头里面蹦出来的(除了跟元素),因此,他必须存在双亲,同时,他有可能存在子树(这里指子节点)。那么,我们就可以得到基本的节点结构如下:
typedef struct TreeNode{
    struct TreeNode *parent;//双亲
    struct TreeNode **childs;//孩子数组
    int childCount;//孩子的数量
    void *data;//节点的数据
}TreeNode;



但是,我们单从节点本身来说,上述的表示方法,存在了很多的冗余信息,因此,我们从最平凡的节点信息来看,也就是说,对于节点,我们只考虑他的双亲和自身的数据,因此,可以表示为下面的结构:
typedef struct SNode{
    struct SNode *parent;//双亲
    void *data;//节点的数据
}SNode;



上述的代码的双亲,我们是用指针来表示的,为了简化我们的表述,我们可以把上述的双亲的指针表述方式换成一个整数型的位置数据来表示(根节点的位置数据为-1)。
 
typedef struct NNode{
   int parentPosition;//双亲
    void *data;//节点的数据
    int32_t curPosition;//当前节点的坐标
}NNode;
 那么,针对我们这章节最开始提到的那颗树,我们可以表示为下面的表格:
curpositon data parent
0 A -1
1 B 0
2 C 0
3 D 1
4 E 1
5 F 2
6 G 2
7 H 3
8 I 3
9 J 3
10 K 6
11 L 6
12 M 6
13 N 6
 
 这种表示方法对我们找到某节点的双亲是很方便的,但是你想一想,要想找到某节点的孩子,是不是很费劲,因此,我们需要做一下改进,也就是说,我们要考虑节点的度的问题,改进后,可以得到下面的节点结构定义:
typedef struct CPNode{
    int32_t parentPosition;//双亲
    void *data;//节点的数据
    int32_t curPosition;//当前节点的坐标
    int32_t *childs;//节点的孩子位置坐标数组
    int32_t degree;//节点的度
}CPNode;



通过这次的改进,我们在某节点上,能很快的找到双亲和子树。为此,我们能够得到最终的树的结构定义:
typedef struct tree{
  int32_t tail;//树的根节点的标号
  int32_t nodeCount;//树的节点数量
  struct CPNode *nodes;//节点数组
}tree;



好啦,我们把这种拓展到一般的情况,得到常规的树节点表示方式和树的表示方式:



typedef struct gTreeNode{
void *data;//节点数据
int32_t degree;//节点的度
struct gTreeNode *parent;//双亲,向前指针
struct gTreeNode *next;//使用链表来存储兄弟节点,向后指针
}gTreeNode;



//树结构定义
typedef struct g{
struct gTreeNode *tail;
int32_t nodes;//树节点数量
}gTreeNode;



 
OK,树的结构已经基本完成了,下面说说一些常规的树的定义(无论他有多么特殊,都可以使用上述的树的相关表示)
 
2.二叉树
二叉树就是在一般树的定义上加了一个限制条件,这个限制条件就是一个节点的度不能超过2.这就是二叉树。
 
在二叉树里面也存在集中特殊的二叉树:
  2.1 斜树:是指二叉树的节点要么只有左子树,要么就只有右子树的情况,就叫做斜树;
  
  2.2满二叉树:是指在二叉树中,如果所有的分支节点都存在左子树和右子树,并且,所有的叶子节点都在同一层上。
 
  2.3 完全二叉树:这个特列是相较于满二叉树来定义的,意思是说,对一个具有n个节点的二叉树,如果编号为i的节点与同样深度的满二叉树中编号为i的节点的二叉树中位置完全相同,那么,这就是二叉树啦,换句话说,完全二叉树是满二叉树的一部分,且所有叶子节点都是在最下面两层,而且最下层的叶子节点,一定是从最左边连续开始的,如果倒数第二层有叶子节点,那么,这些节点就应该是在右部的连续位置,如果节点的度为1,那么这个节点只能有一个左孩子。
那么,针对二叉树,到底有哪些性质呢?
性质1:二叉树的第i层上最多有个节点。
性质2:深度为K的二叉树,最多有-1个节点。
        一层:2^0=1=2^0=2^1-1
        二层:1+2^(2-1)=1+2^1=2^2-1
        三层:2^2-1+2^(3-1)=2^3-1
性质3:如果一颗二叉树的终端节点为m,度为2的节点数量为n,那么,m=n+1;
    这个性质是怎么得到的呢?我们知道,对一颗二叉树来说,树的节点分为三种情况:度为1的节点n0、叶子节点m、度为2的节点n,那么树的节点数量T=n0+m+n.
  同时,我们知道,所有二叉树节点间的连线的数量时等于总节点数减1的。同时,我们也知道,对于一个度为2的节点,他的出线应该是2条,因此,度为2的节点对应的连线应该=2n.而对于终端节点是没有出线的,对于度为1的节点,他的出线只有1,因此,从连线的角度来看节点的数量T=2n+n0+1,因此,可以得到n0+m+n=2n+n0+1,从而得到m=n+1;
      性质4:具有n个节点的完全二叉树的深度为 +1.
       怎么算出来的?我们知道,一个满二叉树的节点数量n= -1,其中k为这个二叉树的度,那么,这里的k= .
      根据完全二叉树的定义,他的节点数量最多是可以等于同样深度的满二叉树节点数量 -1的,但是一定是大于 .也就是说 ,因为n必须是整数,可以取对数,就可以得到上面的结论。
 
 
2.4 二叉树的结构和存储
   通过上面的学习,我们知道,二叉树中的节点有应该具备四个属性:数据域、左孩子、右孩子、双亲,因此,对于二叉树来说,我们可以重新定义上面提到的树的节点结构的定义:
typedef struct BiTNode{
    void *data;//数据域
    struct BiTNode *left;//左孩子
    struct BiTNode *right;//右孩子
    struct BiTNode *parent;//双亲
}BiTNode;



2.5 遍历二叉树
   学习到这里,树以及二叉树相关的概念和定义已经搞定,那么,针对一个树来说,我们要遍历其中的节点,怎么办呢?我记得我在读本科的时候,有次考试就是考了这种题目,NND,当时不是很清楚,结果可想而知。
 在遍历二叉树的时候,我们采用的方法取决于我们选择的方向。
我们先看一颗二叉树,然后再一个方法一个方法的来看是怎么实现的
 
//二叉树、节点定义
typedef struct BiTNode{
   void *data;//数据域
    struct BiTNode *left;//左孩子
    struct BiTNode *right;//右孩子
    struct BiTNode *parent;//双亲
}BiTNode,*BiTree;
2.5.1 前序遍历
    前序遍历的规则就是从根节点开始,如果二叉树为空,则直接返回,否则 先访问根节点,然后前序遍历左子树,再前序遍历右子树。
  
得到的结果是:ABDHIEJCFG
//前序遍历二叉树
void preOrderTraverse(BiTree t){
    if(NULL==t||NULL==t->data) return ;
    //操作每个节点,比如说是打印节点
    printf("%s",t->data);
    preOrderTraverse(t->left);
    preOrderTraverse(t->right);
}


2.5.2 中序遍历

      中序遍历的规则就是从根节点开始,如果二叉树为空,则直接返回,否则从 根节点开始(并不是先访问根节点),中序遍历根节点的左子树,然后访问根节点,最后访问根节点的右子树。
最终的结果是HDIBJEAFCG
 
//中序遍历二叉树
void inOrderTraverse(BiTree t){
    if(NULL==t||NULL==t->data) return ;
    inOrderTraverse(t->left);
    //操作每个节点,比如说是打印节点
    printf("%s",t->data);
    inOrderTraverse(t->right);
}



2.5.3 后序遍历
    后序遍历的规则是,如果树为空,则直接返回,否则从左到右先叶子后节点的方式来访问左右子树,最后访问根节点。
最终的访问结果是:HIDJEBFGCA
//后序遍历二叉树
void inOrderTraverse(BiTree t){
    if(NULL==t||NULL==t->data) return ;
    inOrderTraverse(t->left);
    inOrderTraverse(t->right);
        //操作每个节点,比如说是打印节点
    printf("%s",t->data);
}



 
2.5.4 层序遍历
  层序遍历的规则是,若果树为空,则直接返回,否则先从根的第一层开始,在访问同一层的时候,先左后右。
 
 
 
我们回到先前定义的二叉树节点,你会发现会存在一个很严重的问题,是什么问题呢?
 我们定义的节点有三个域,一个是左孩子指针域,一个是右孩子指针域,另外是数据域。但是,我们看一个二叉树的例子,就能清楚的发现这种做法,有一个很大的弊端。
 
(注意:上图我是忽略了每个节点的双亲指针域的情况了的展现情况)我们看到上面的很多节点的指针域是没有充分利用起来的,怎么办呢?我们知道,对于一个有n个节点的二叉树,一共有2n个指针域,同时又n-1条连线,也就是说存在2n-(n-1)=n+1个空指针域,上面的树节点的空指针域有11个空指针域。
  我们用中序遍历来遍历上面的二叉树,得到的结果是HDIBJEAFCG,问题来了,你能很容易的知道任意节点的前驱和后继么?如果想要知道,我们必须得先遍历一次才知道,因此,我们可以想象一下,在建立节点的时候,是不是可以明确的标注呢?我们因此把这种具有前驱和后继的树称作线索二叉树。
改进后,我们得到的节点的结构定义就变成了下面的定义:
/**
* Link=0 表示左右孩子指针标示
*Thread=1 表示前驱或后继指针标示
*/
typedef enum {Link,Thread} Tag;
typedef struct tagBiTreeNode{
    struct tagBiTreeNode *left;
    struct tagBiTreeNode *right;
    void *data;
    Tag LTag;
    Tag RTag;
}tagBiTreeNode,*tagBiTree;



 
好啦,二叉树的内容基本搞定了,但是你发现没有,我们针对的实现基本都是基于二叉树的,但是,我们平时生活中的又有多少是满足二叉树结构的呢?我们能否把常规的树转化为 二叉树呢?
 
3.树、森林、二叉树的转换
   我把后面的内容放在这个章节的后续章节来说吧,貌似这章节的内容太多了
 
 
很多东西可能会没有说清楚,欢迎发表意见,同时可以加QQ:359311095探讨

© 著作权归作者所有

共有 人打赏支持
会飞的杨先生
粉丝 9
博文 14
码字总数 30689
作品 0
昆明
CTO(技术副总裁)
求Tree的Cache数据结构设计思路

背景: 数据示例:中国行政区树形结构,一直到街道(乡村) 使用MySQL作为存储,字段如下: 为减少对数据库的请求量,需要将这些数据存储在Cache中,比如Redis、Memcache等。 大家可以忽略l...

会员 ⋅ 2014/12/18 ⋅ 5

java collection 集合源码分析(三) map

TreeMap 首先看下TreeMap的头部声明的两个变量,TreeMap的排序利用红黑树进行 /** * The comparator used to maintain order in this tree map, or * null if it uses the natural ordering ......

nero_zy ⋅ 2015/09/01 ⋅ 2

skiplist(跳表)算法实现

跳表是平衡树的一种替代的数据结构,但是和红黑树不相同的是,跳表对于树的平衡的实现是基于一种随机化的算法的,这样也就是说跳表的插入和删除的工作是比较简单的。 下面来研究一下跳表的核...

golang_yh ⋅ 2016/01/27 ⋅ 0

2016个人计划

================2015总结============================ 算完成了吧 1:找个女朋友 。。。 未完成 2:养好身体 未完成 未完成 3:深入了解java基础,看看jdk1.6,1.7的新特性,了解多线程,高...

有种下班别走 ⋅ 2016/02/16 ⋅ 0

BlackHole开发日记-设置多个外部DNS并选择

2012-12-22 今天做了一天家务,周末比上班还忙啊。晚上9点半开始写了点代码,想把外部DNS选择机制改为:最短请求时间。 晚上从9点开始写代码,终于到12点写完了。开始尝试用TreeMap做一个按照...

黄亿华 ⋅ 2012/12/23 ⋅ 0

谷歌Jeff Dean团队发文,探讨「学习模型」如何替代传统索引结构

原文来源:arxiv-vanity 作者:Tim Kraska、Alex Beutel、Ed H. Chi、Jeffrey Dean、Neoklis Polyzotis 「雷克世界」编译:嗯~阿童木呀、多啦A亮、我是卡布达 索引就是模型:B-Tree-Index可以...

cf2suds8x8f0v ⋅ 2017/12/13 ⋅ 0

关于PriorityQueue 二叉堆的问题

场景:最近在研究java中的队列,当研究到优先队列的时候去读 PriorityQueue的源码的时候发现一种数据结构,我数据结构这块基本上上是空白,所以让我晦涩难懂啊,于是我查阅了大量资料以及手动...

skyline520 ⋅ 2013/06/01 ⋅ 0

redis更新日志中文版2.4-2.6

2.4 -> 2.6 1.SORT命令不会对非数值类型(double)排序,适用于list,set (string 类型使用 sort alpha ) 2.EXPIRE相关命令都精确到了毫秒,不影响expire命令 3.INFO输出格式中增加了空行与注释...

屌丝Lee ⋅ 2016/06/15 ⋅ 0

阿里Java工程师分享3年工作经验的程序员应该具备的技能

本文转载自:阿里Java工程师分享3年工作经验的程序员应该具备的技能 每个程序员、或者说每个工作者都应该有自己的职业规划,如果你不是富二代,不是官二代,也没有职业规划,希望你可以思考一...

gongxifacai_believe ⋅ 2017/12/26 ⋅ 0

3年工作经验的程序员应该具备的技能

点击上方“程序员大咖”,选择“置顶公众号” 关键时刻,第一时间送达! 工作才是生存的唯一依靠 每个程序员、或者说每个工作者都应该有自己的职业规划,如果你不是富二代,不是官二代,也没...

px01ih8 ⋅ 2017/12/14 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

面试-JVM 内存结构

JVM 内存结构

秋日芒草 ⋅ 8分钟前 ⋅ 0

马氏距离与欧氏距离

马氏距离 马氏距离也可以定义为两个服从同一分布并且其协方差矩阵为Σ的随机变量之间的差异程度。 如果协方差矩阵为单位矩阵,那么马氏距离就简化为欧氏距离,如果协方差矩阵为对角阵,则其也...

漫步当下 ⋅ 31分钟前 ⋅ 0

聊聊spring cloud的RequestRateLimiterGatewayFilter

序 本文主要研究一下spring cloud的RequestRateLimiterGatewayFilter GatewayAutoConfiguration @Configuration@ConditionalOnProperty(name = "spring.cloud.gateway.enabled", matchIfMi......

go4it ⋅ 今天 ⋅ 0

Spring JavaConfig 注解

JavaConfig注解允许开发者将Bean的定义和配置放在Java类中。它是除使用XML文件定义和配置Bean外的另一种方案。 配置: 如一个Bean如果在XML文件可以这样配置: <bean id="helloBean" class="...

霍淇滨 ⋅ 今天 ⋅ 0

Spring clound 组件

Spring Cloud技术应用从场景上可以分为两大类:润物无声类和独挑大梁类。 润物无声,融合在每个微服务中、依赖其它组件并为其提供服务。 Ribbon,客户端负载均衡,特性有区域亲和、重试机制。...

英雄有梦没死就别停 ⋅ 今天 ⋅ 0

Confluence 6 重新获得站点备份文件

Confluence 将会创建备份,同时压缩 XML 文件后存储熬你的 <home-directory>/backups> 目录中。你需要自己访问你安装的 Confluence 服务器,并且从服务器上获得这个文件。 运行从 Confluence...

honeymose ⋅ 今天 ⋅ 0

informix的常用SQL语句

1、创建数据库 eg1. 创建不记录日志的库testdb,参考语句如下: CREATE DATABASE testdb; eg2. 创建带缓冲式的记录日志的数据库testdb(SQL语句不一定在事务之中,拥有者名字不被用于对象的解...

wangxuwei ⋅ 今天 ⋅ 0

matplotlib画图

最简单的入门是从类 MATLAB API 开始,它被设计成兼容 MATLAB 绘图函数。 from pylab import *from numpy import *x = linspace(0, 5, 10)y = x ** 2figure()plot(x, y, 'r')...

Dr_hu ⋅ 今天 ⋅ 0

RabbitMQ学习以及与Spring的集成(三)

本文介绍RabbitMQ与Spring的简单集成以及消息的发送和接收。 在RabbitMQ的Spring配置文件中,首先需要增加命名空间。 xmlns:rabbit="http://www.springframework.org/schema/rabbit" 其次是模...

onedotdot ⋅ 今天 ⋅ 0

JAVA实现仿微信红包分配规则

最近过年发红包拜年成为一种新的潮流,作为程序猿对算法的好奇远远要大于对红包的好奇,这里介绍一种自己想到的一种随机红包分配策略,还请大家多多指教。 算法介绍 一、红包金额限制 对于微...

小致dad ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部