目录
1,树的概念
1、树的特性
1)一棵树中的任意两个结点有且仅有唯一的一条路径连通;
2)一棵树如果有n个结点,则它一定有n−1条边;
3)在一棵树中加一条边将会构成一个回路。
2、二叉树
1)二叉树是一种特殊的树,二叉树的特点是每个结点最多有两个儿子。
2)二叉树使用范围最广,一颗多叉树也可以转化为二叉树。
3、满二叉树
1)二叉树中每个内部节点都有两个儿子,满二叉树所有的叶节点都有相同的深度。
2)满二叉树是一棵深度为h且有2h−1个结点的二叉树。
4、完全二叉树
1)若设二叉树的高度为h,除了第h层外,其他层的结点数都达到最大个数,第h层从右向左连续 缺若干个结点,则为完全二叉树。
5、树的特点
- 如果一棵完全二叉树的父节点编号为K,则其左儿子的编号是2K,右儿子的结点编号为2K+1
- 已知完全二叉树的总节点数为n求叶子节点个数:
- 已知完全二叉树的总节点数为n求父节点个数:为:n/2
- 已知完全二叉树的总节点数为n求叶子节点为2的父节点个数:
当n为奇数时:n/2
当n为偶数时 : n/2-1
5.如果一棵完全二叉树有N个结点,那么这棵二叉树的深度为【log2(N+1)log2(N+1)】(向上取整)
2,二叉树基本操作
参考博客:https://www.cnblogs.com/freeman818/p/7252041.html
1、生成树结构
- 前序遍历: DBACEGF(根节点排最先,然后同级先左后右)
- 中序遍历: ABCDEFG (先左后根最后右)
- 后序遍历: ACBFGED (先左后右最后根)
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
def preTraverse(root):
'''
前序遍历
'''
if root==None:
return
print(root.value)
preTraverse(root.left)
preTraverse(root.right)
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
print('前序遍历:')
preTraverse(root) # DBACEGF
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
def midTraverse(root):
'''
中序遍历
'''
if root == None:
return
midTraverse(root.left)
print(root.value)
midTraverse(root.right)
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
print('中序遍历:')
midTraverse(root) # ACBFGED
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
def afterTraverse(root):
'''
后序遍历
'''
if root == None:
return
afterTraverse(root.left)
afterTraverse(root.right)
print(root.value)
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
print('后序遍历:')
afterTraverse(root) # ACBFGED
前序排列原理:
#####此时执行preTraverse(root.left) 函数
'''
1、第一步 root=Node(D) print D,D入栈[D]
2、第二步 root=Node(D).left=Node(B) print B, B入栈[D,B]
3、第三步 root=Node(B).left=Node(A) print A, A入栈[D,B,A]
4、第四步 root=Node(A).left=None,没有进入递归,顺序执行preTraverse(root.right)
5、第五步 Node(A).right==None,也没有进入递归,此时preTraverse(A) 函数才会正真返回,A出栈[D,B]
6、第六步 A的上级调用函数为:preTraverse(B.left),所以接着会顺序执行preTraverse(B.right),B的左右节点访问后B出栈[D]
7、第七步 Node(B).right==Node(C) print C,C入栈[D,C]
8、第八步 Node(C).left==None, Node(C).right==None,访问完C的左右节点后函数返回C出栈,返回上级调用[D]
9、第九步 此时返回上级调用执行preTraverse(D.right)=Node(E) print E,D出栈,E入栈[E]
'''
'''此时输出结果:DBACE'''
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
def layered_print( root):
if not root:
return []
curLayer = [root] # 当前层的所有节点
while curLayer:
layerValue = [] # 当前层的值
nextLayer = [] # 下一层的所有节点
for node in curLayer: # 循环当前层所有节点并并获取所有value值
layerValue.append(node.value)
if node.left:
nextLayer.append(node.left) # 将当前层的左节点加入列表
if node.right:
nextLayer.append(node.right) # 将当前层的右节点加入列表
print layerValue # 打印当前层的值
curLayer = nextLayer # 将循环下移一层
'''
['D']
['B', 'E']
['A', 'C', 'G']
['F']
'''
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
layered_print(root)
3,hash树
1、hash树描述(就是散列树)
- 散列树选择从2开始的连续质数来建立一个十层的哈希树。
- 第一层结点为根结点,根结点下有2个结点;
- 第二层的每个结点下有3个结点;
- 依此类推,即每层结点的子节点数目为连续的质数。
2、hash树特点
注:关系型数据库中,索引大多采用B/B+树来作为存储结构,而全文搜索引擎的索引则主要采用hash的存储结构,这两种数据结构有什么区别?
- 如果是等值查询,那么哈希索引明显有绝对优势,因为只需要经过一次算法即可找到相应的键值;
- 当然了,这个前提是,键值都是唯一的,如果键值不是唯一的,就需要先找到该键所在位置,然后再根据链表往后扫描,直到找到相应的数据;
- 如果是范围查询检索,这时候哈希索引就毫无用武之地了,因为原先是有序的键值,经过哈希算法后,有可能变成不连续的了,就没办法再利用索引完成范围查询检索;
- 同理,哈希索引也没办法利用索引完成排序,以及like ‘xxx%’ 这样的部分模糊查询(这种部分模糊查询,其实本质上也是范围查询);
3、建立hash树
- 选择从2开始的连续质数来建立一个十层的哈希树。
- 第一层结点为根结点,根结点下有2个结点;第二层的每个结点下有3个结点;
- 依此类推,即每层结点的子节点数目为连续的质数。到第十层,每个结点下有29个结点。
- 同一结点中的子结点,从左到右代表不同的余数结果。
例如:第二层结点下有三个子节点。那么从左到右分别代表:除3余0,除3余1,除3余2.对质数进行取余操作得到的余数决定了处理的路径。
- 以随机的10个数的插入为例,来图解HashTree的插入过程。
- 其实也可以把所有的键-值节点放在哈希树的第10层叶节点处,这第10层的满节点数就包含了所有的整数个数,
但是如果这样处理的话,所有的非叶子节点作为键-值节点的索引,这样使树结构庞大,浪费空间。
4、查找编辑
- 哈希树的节点查找过程和节点插入过程类似,就是对关键字用质数序列取余,根据余数确定下一节点的分叉路径,直到找到目标节点。
- 如上图,最小”哈希树(HashTree)在从4G个对象中找出所匹配的对象,比较次数不超过10次,也就是说:最多属于O(10)。
- 在实际应用中,调整了质数的范围,使得比较次数一般不超过5次。
- 也就是说:最多属于O(5),因此可以根据自身需要在时间和空间上寻求一个平衡点。
5、删除编辑
- 哈希树的节点删除过程也很简单,哈希树在删除的时候,并不做任何结构调整。
- 只是先查到到要删除的节点,然后把此节点的“占位标记”置为false即可(即表示此节点为空节点,但并不进行物理删除)。
6、hash树优点
- 从哈希树的结构来说,非常的简单,每层节点的子节点个数为连续的质数。
- 子节点可以随时创建,因此哈希树的结构是动态的,也不像某些哈希算法那样需要长时间的初始化过程。
- 哈希树也没有必要为不存在的关键字提前分配空间。
- 从算法过程我们可以看出,对于整数,哈希树层级最多能增加到10。
- 因此最多只需要十次取余和比较操作,就可以知道这个对象是否存在,这个在算法逻辑上决定了哈希树的优越性。
- 从删除算法中可以看出,哈希树在删除的时候,并不做任何结构调整。
- 常规树结构在增加元素和删除元素的时候都要做一定的结构调整,否则他们将可能退化为链表结构,而导致查找效率的降低。
- 哈希树采取的是一种“见缝插针”的算法,从来不用担心退化的问题,也不必为优化结构而采取额外的操作,因此大大节约了操作时间。
7、缺点编辑
- 哈希树不支持排序,没有顺序特性。
- 如果在此基础上不做任何改进的话并试图通过遍历来实现排序,那么操作效率将远远低于其他类型的数据结构。
8、hash索引使用范围
总结:哈希适用在小范围的精确查找,在列数据很大,又不需要排序,不需要模糊查询,范围查询时有用
1、hash索引仅满足“=”、“IN”和“<=>”查询,不能使用范围查询
因为hash索引比较的是经常hash运算之后的hash值,因此只能进行等值的过滤,不能基于范围的查找,
因为经过hash算法处理后的hash值的大小关系,并不能保证与处理前的hash大小关系对应。
2、hash索引无法被用来进行数据的排序操作
由于hash索引中存放的都是经过hash计算之后的值,而hash值的大小关系不一定与hash计算之前的值一样,
所以数据库无法利用hash索引中的值进行排序操作。
3、对于组合索引,Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值,
而不是单独计算 Hash 值,所以通过组合索引的前面一个或几个索引键进行查询的时候,Hash 索引也无法被利用。
4、Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。
对于选择性比较低的索引键,如果创建 Hash 索引,那么将会存在大量记录指针信息存于同一个 Hash 值相关联。
这样要定位某一条记录时就会非常麻烦,会浪费多次表数据的访问,而造成整体性能低下。