数据结构中的树

内容包括数据结构中树的基本概念,实现与应用,以及二叉树,表达式树,二叉查找树,AVL树,伸展树,B+树,以及Java中HashMap的内部实现结构。

 

数据结构中树的基本概念

树的预备知识

的递归方式定义:一棵树是一些节点的集合。这些集合可以是空集,若不是空集,则由称作的节点r以及0个或者多个非空的(子树)T1,T2,….Tk组成,这些子树中每一棵的根都被来自根r的一条有向的边所连接。

一个树是由N个节点和N-1条边的集合。(每条边都将由某个节点连接到它的父亲,而除去根节点外每一个节点都有一个父亲)

没有儿子的节点称为树叶(叶节点),具有相同父亲节点的节点为兄弟

从节点n1到nk的路径定义为节点n1,n2,…,nk的一个序列,使得对于1<=i长是为该路径上边的条数,即k-1。在一棵树中从根到每个节点恰好存在一条路径。

对任意节点ni,ni的深度为从根到ni的唯一路径的长。ni的是从ni到一片树叶的最长路径的长。(不同的书定义不一样,知道这个概念就好) 参考《Data Structures and Algorithm Anylysis in Java》

树的实现

一种简单的实现方式:将每个节点的所有儿子都放在树节点的链表中。

其中firstChild(第一个儿子)的链,nextSibling(下一个兄弟)的链。

tree-firstchild-nextsibling

如上图所示,E有一个链指向第一个儿子(H),也有一个链指向下一个兄弟(F)。

 

树的应用

先序遍历:访问根节点;访问根节点的左子树;访问根节点的右子树

一个应用就是列出目录中的所有文件的名字:

后序遍历:访问根节点的左子树;访问根节点的右子树;访问根节点

一个应用就是算出磁盘的大小:

中序遍历:访问根节点的的左子树;访问根节点;访问根节点的右子树。

 

二叉树

二叉树是一棵树,其中每个节点都不能有多余两个儿子。

具有N个节点的每一棵二叉树都将需要N+1个null链。(2N(总边树) – (N – 1)(树的边数))

 

表达式树

表达式树:树叶是操作数(常数或者是变量名),而其他节点为操作符。

对表达式树进行中序遍历就能到了中缀表达式,后序遍历则是后缀表达式。

expression-tree

上图为(a+b*c)+((d*e+f)*g)的表达式树。

构造表达式树

对于一个后缀表达式。如果符号的操作数,则建立一个单节点并将它推入栈中,如果符号的操作数,那么就从栈中弹出两棵树T1和T2(先弹出的为右子树)并形成一棵新的树,该树的根就是操作符。

 

二叉查找树

使二叉树成为二叉查找树的性质是,对于树中的每个节点X,它的左子树中所有的项的值都小于X,它的右子树中所有项的值都大于X。二叉查找树的平均深度为O(logN)

代码实现:

 

AVL树

REFhttp://blog.csdn.net/pacosonswjtu/article/details/50522677

一个AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树。

插入一个节点可能破坏AVL树的特性,而这总可以通过对树进行简单的修正来做到,我们称其为旋转

单旋转:插入点不介于不满足AVL条件的树根和树根对应孩子节点之间

双旋转:插入点介于不满足AVL条件的树根和树根对应孩子节点之间

旋转轴:插入点的直接父节点

不满足AVL条件的树根:深度最深的那个不满足AVL条件的节点

 

伸展树

伸展树的想法是,当一个节点被访问后,它就要经过一系列的AVL树的旋转被推到根上。

 

B+树

大O分析假设所有的操作耗时都是相等的,但是当涉及到磁盘I/O的时候,对于磁盘的访问就非常耗时,因此为了节省磁盘访问,我们愿意进行大量的计算。

B+树:是应文件系统所需而产生的一种B-tree的变形树(多叉树)。内部节点不保存信息,叶子节点保存一个磁盘区域。

为什么说B+树比B树更适合实际应用中操作系统的文件索引和数据库索引?

REFhttp://blog.csdn.net/v_july_v/article/details/6530142

  • B+树的磁盘读写代价更低

B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

  • B+树的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

数据库索引采用B+树的主要原因是 B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题,B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作(或者说效率太低)。

Java中的HashMap

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

Initial capacity: The capacity is the number of buckets in the hash table, The initial capacity is simply the capacity at the time the hash table is created.

Load factor: The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

HashMap内部是通过哈希表来存储的,所谓哈希表其实就是数组+链表。通过哈希值来计算数组下标,再通过链表的形式将Entry存在相应的数组位置。

HashMap内部数据结构

 

HashMap的put方法

 

HashMap的get方法

 

HashMap的hash函数

hashmap-hash

算下标的时候是通过(n – 1) & hash来算的,如果n比较小,例如15(0x1111)那么真正起效的只有低4位的值,容易碰撞。因此设计者使用了高16和低16异或了一下。

 

HashMap的resize方法

 

Telegram频道已经开通,关注flyzythink,随手分享正能量,了解VPS优惠与补货
Telegram群组已经开通,加入flyzy小站,FREE TO TALK
QQ群开通:780593286 flyzy小站
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注