华图事业单位官网
2014-09-27 15:14:50 事业单位考试网 https://sydw.huatu.com/ 文章来源:华图教育
【导读】华图事业单位考试网同步华图教育发布:2015年国家电网考试备考计算机之数据结构与算法(7),详细信息请阅读下文!事业单位考试考情政策解读,点击领取备考资料,更多事业单位考试资讯请关注(htshiyedanwei)公众号,欢迎加入事业单位招聘考试交流群: 参加刷题、模考、领取备考资料,考编路上不孤单!
5.树 (Tree)
数据结构中为了存储和查找的方便,用各种树结构来存储文件。树结构包括:二叉查找树(二叉排序树)、平衡二叉树(AVL树)、红黑树、B-树、B+树、字典树(trie树)、后缀树、广义后缀树。各种树的表示方法、特点及各自的用途如下:
1、二叉查找树(二叉排序树)
(图a)
二叉查找树是一种动态查找表(图a),具有这些性质:
(1)若它的左子树不为空,则左子树上的所有节点的值都小于它的根节点的值;
(2)若它的右子树不为空,则右子树上所有节点的值都大于它的根节点的值;
(3)其他的左右子树也分别为二叉查找树;
(4)二叉查找树是动态查找表,在查找的过程中可见添加和删除相应的元素,在这些操作中需要保持二叉查找树的以上性质。
2、平衡二叉树(AVL树)
(图b)
含有相同节点的二叉查找树可以有不同的形态,而二叉查找树的平均查找长度与树的深度有关,所以需要找出一个查找平均长度最小的一棵,那就是平衡二叉树(图b),具有以下性质:
(1)要么是棵空树,要么其根节点左右子树的深度之差的绝对值不超过1;
(2)其左右子树也都是平衡二叉树;
(3)二叉树节点的平衡因子定义为该节点的左子树的深度减去右子树的深度。则平衡二叉树的所有节点的平衡因子只可能是-1,0,1。
3、红黑树
(图c)
红黑树是一种自平衡二叉树,在平衡二叉树的基础上每个节点又增加了一个颜色的属性,节点的颜色只能是红色或黑色。具有以下性质:
(1)根节点只能是黑色;
(2)红黑树中所有的叶子节点后面再接上左右两个空节点,这样可以保持算法的一致性,而且所有的空节点都是黑色;
(3)其他的节点要么是红色,要么是黑色,红色节点的父节点和左右孩子节点都是黑色,及黑红相间;
(4)在任何一棵子树中,从根节点向下走到空节点的路径上所经过的黑节点的数目相同,从而保证了是一个平衡二叉树。
4、B-树
手机端链接:https://m.sydw.huatu.com/2014/0927/1070701.html
官方微信号
官方微博号
事业单位考试推荐 | |||||
热点考试 | |||||
招考公告 | 职位表 | 报名时间 | 报名条件 | 报名入口 | |
考试时间 | 缴费入口 | 考试科目 | 考试大纲 | 报考指导 | |
准考证 | 成绩查询 | 资格复审 | 面试公告 | 工资待遇 | |
实用备考 | |||||
每日直播 | 时政周播 | 领资料包 | 试题资料 | 备考指导 | |
图书购买 | 笔试课程 | 面试课程 | 网络课程 | 更多>>> |
事业单位微信
事业单位微博号