搜索
房产
装修
汽车
婚嫁
健康
理财
旅游
美食
跳蚤
二手房
租房
招聘
二手车
教育
茶座
我要买房
买东西
装修家居
交友
职场
生活
网购
亲子
情感
龙城车友
找美食
谈婚论嫁
美女
兴趣
八卦
宠物
手机

基础数据结构 例:栈、队列、链表、数据、字典、树、等

[复制链接]
查看: 25|回复: 0

1万

主题

1万

帖子

4万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
45261
发表于 2020-2-14 20:09 | 显示全部楼层 |阅读模式
目录
数据结构:

行列
链表
3.1 单向链表
3.2 双向链表
3.3 单向链表反转
数组
字典实现道理
5.1 哈希表
5.2 哈希函数

6.1 二叉树、满二叉树、完全二叉树
6.2 hash树
6.3 B-tree/B+tree

栈 stack
栈(stack)别名仓库,它是一种运算受限的线性表。限制仅在表尾举行插入和删除操纵的线性表。这一端被称为栈顶,把另一端称为栈底。向一个栈插入新元素又称作 进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删撤除,使其相邻的元素成为新的栈顶元素。
栈作为一种数据结构,是一种只能在一端举行插入和删除操纵的出格线性表。它依照先辈后出的原则存储数据,先辈入的数据被压入栈底,末端的数据在栈顶,需要读数据的时候从栈顶起头弹出数据(末端一个数据被第一个读出来)。栈具有记忆感化,对栈的插入与删除操纵中,不需要改变栈底指针。
栈是答应在同一端举行插入和删除操纵的出格线性表。答应举行插入和删除操纵的一端称为栈顶(top),另一端为栈底(bottom);栈底牢固,而栈顶浮动;栈中元素个数为零时称为空栈。插入一样平常称为进栈(PUSH),删除则称为退栈(POP)。栈也称为先辈后出表。
栈可以用来在函数挪用的时候存储断点,做递归时要用到栈!
基础数据结构 例:栈、队列、链表、数据、字典、树、等  热点新闻 1866130-20200214110817718-1169569662





栈的特点:
落后先出,末端插入的元素起头出来。
Python实现
  1. # 栈的次第表实现class Stack(object):def __init__(self):self.items = []def isEmpty(self):return self.items == []def push(self, item):return self.items.append(item)def pop(self):return self.items.pop()def top(self):return self.items[len(self.items)-1]def size(self):return len(self.items)if __name__ == '__main__':stack = Stack()stack.push("Hello")stack.push("World")stack.push("!")print(stack.size())print(stack.top())print(stack.pop())print(stack.pop())print(stack.pop())# 成果3!!WorldHello
复制代码
  1. # 栈的链接表实现class SingleNode(object):def __init__(self, item):self.item = itemself.next = Noneclass Stack(object):def __init__(self):self._head = Nonedef isEmpty(self):return self._head == Nonedef push(self, item):node = SingleNode(item)node.next = self._headself._head = nodedef pop(self):cur = self._headself._head = cur.nextreturn cur.itemdef top(self):return self._head.itemdef size(self):cur = self._headcount = 0while cur != None:count += 1cur = cur.nextreturn countif __name__ == '__main__':stack = Stack()stack.push("Hello")stack.push("World")stack.push("!")print(stack.size())print(stack.top())print(stack.pop())print(stack.pop())print(stack.pop())# 成果3!!WorldHello
复制代码
行列
行列是一种特此外线性表,出格之处在于它只答应在表的前端(front)举行删除操纵,而在表的后端(rear)举行插入操纵,和栈一样,行列是一种操纵受限制的线性表。举行插入操纵的端称为队尾,举行删除操纵的端称为队头。行列中没有元素时,称为空行列。
行列的数据元素又称为行列元素。在行列中插入一个行列元素称为入队,从行列中删除一个行列元素称为出队。由于行列只答应在一端插入,在另一端删除,所以只要最早进入行列的元素才华起头从行列中删除,故行列又称为先辈先出(FIFO—first in first out)线性表.
基础数据结构 例:栈、队列、链表、数据、字典、树、等  热点新闻 1866130-20200214111926583-187563906

行列的特点:
先辈者先出,起头插入的元素起头出来。
我们可以设想成,排队买票,先来的先买,后来的只能在末端,不答应插队。
行列的两个底子操纵:入队 将一个数据放到行列尾部;出队 从行列的头部取出一个元素。行列也是一种操纵受限的线性表数据结构 它具有先辈先出的特征,支持队尾插入元素,在队头删除元素。
行列的概念很好大白,行列的利用也很是普遍如:循环行列、阻塞行列、并发行列、优先级队列等。下面将会先容。
次第行列:
次第行列就是我们常说的 “FIFO”(先辈先出)行列,它严重包含的方式有:取第一个元素(first方式)、进入行列(enqueue方式)、出行列(dequeue方式)、清空行列(clear方式)、判定行列能否为空(empty方式)、获得行列长度(length方式),具体的实现看下面的源代码。一样,这里在取行列的第一个元素、以及出行列的时候,也需要判定下行列能否为空。
  1. class Queue:"""次第行列实现"""def __init__(self):"""初始化一个空行列,由于行列是私有的"""self.__queue = []def first(self):"""获得行列的第一个元素:return:假如行列为空,则返回None,否则返回第一个元素"""return None if self.isEmpty() else self.__queue[0]def enqueue(self, obj):"""将元素加入行列:param obj:要加入行列的工具"""self.__queue.append(obj)def dequeue(self):"""从行列中删除第一个元素:return:假如行列为空,则返回None,否则返回dequeued元素"""return None if self.isEmpty() else self.__queue.pop(0)def clear(self):"""扫除全部行列"""self.__queue.clear()def isEmpty(self):"""判定行列能否为空返回:bool值"""return self.length() == 0def length(self):"""获得行列长度并返回"""return len(self.__queue)
复制代码
优先行列:
优先行列简单说就是一个有序行列,排序的法则就是自界说的优先级巨细。鄙人面的代码实现中,严重利用的是数值巨细举行比力排序,数值越小则优先级越高,理论上应当把优先级高的放在行列首位。值得留意的是,笔者这里用list来实现的时候恰恰次第是反的,即list中元素是从大到小的次第,这样做的好处是取行列的第一个元素、以及出行列这两个操纵的时候复杂度为O(1),仅仅入行列操纵的时候复杂度为O(n)。假如是依照从小到大的次第,那末将会发生两个时候复杂度为O(n),一个时候复杂度为O(1)。
  1. class PriorQueue:"""优先行列实现"""def __init__(self, objs=[]):"""初始化优先行列,默许行列为空:参数objs:工具列表初始化"""self.__prior_queue = list(objs)# 排序从最大值到最小值,最小值具有最高的优先级# 使得“dequeue”的服从为O(1)self.__prior_queue.sort(reverse=True)def first(self):"""获得优先行列的最高优先级元素O(1):return:假如优先行列为空,则返回None,否则返回优先级最高的元素"""return None if self.isEmpty() else self.__prior_queue[-1]def enqueue(self, obj):"""将一个元素加入优先行列,O(n):param obj:要加入行列的工具"""index = self.length()while index > 0:if self.__prior_queue[index - 1] < obj:index -= 1else:breakself.__prior_queue.insert(index, obj)def dequeue(self):"""从优先行列中取出最高优先级的元素,O(1):return:假如优先行列为空,则返回None,否则返回dequeued元素"""return None if self.isEmpty() else self.__prior_queue.pop()def clear(self):"""扫除全部优先行列"""self.__prior_queue.clear()def isEmpty(self):"""判定优先行列能否为空返回:bool值"""return self.length() == 0def length(self):"""获得优先行列的长度返回:"""return len(self.__prior_queue)
复制代码
循环行列:
循环行列,就是将普通的行列首尾毗连起来, 构成一个环状,并别离设备首尾指针,用来指明行列的头和尾。每当我们插入一个元素,尾指针就向后移动一位,固然,在这里我们行列的最大长度是提早界说好的,当我们弹出一个元素,头指针就向后移动一位。
这样,列表中就不存在删除操纵,只要点窜操纵,从而制止了删除前面节点酿成的价格大的题目。
基础数据结构 例:栈、队列、链表、数据、字典、树、等  热点新闻 1866130-20200214113005870-343574249
  1. class Loopqueue:'''循环行列实现'''def __init__(self, length):self.head = 0self.tail = 0self.maxSize = lengthself.cnt = 0self.__list = [None]*lengthdef __len__(self):'''界说长度'''return self.cntdef __str__(self):'''界说返回值 典范'''s = ''for i in range(self.cnt):index = (i + self.head) % self.maxSizes += str(self.__list[index])+' 'return sdef isEmpty(self):'''判定能否为空'''return self.cnt == 0def isFull(self):'''判定能否装满'''return self.cnt == self.maxSizedef push(self, data):'''增加元素'''if self.isFull():return Falseif self.isEmpty():self.__list[0] = dataself.head = 0self.tail = 0self.cnt = 1return Trueself.tail = (self.tail+1)%self.maxSizeself.cnt += 1self.__list[self.tail] = datareturn Truedef pop(self):'''弹出元素'''if self.isEmpty():return Falsedata = self.__list[self.head]self.head = (self.head+1)%self.maxSizeself.cnt -= 1return datadef clear(self):'''清空行列'''self.head = 0self.tail = 0self.cnt = 0return True
复制代码
阻塞行列
阻塞行列是一个在行列根柢上又支持了两个附加操纵的行列。
阻塞(并发)行列与普通行列的区分在于,当行列是空的时,从行列中获得元素的操纵将会被阻塞,大要当行列是满时,往行列里增加元素的操纵会被阻塞。试图从空的阻塞行列中获得元素的线程将会被阻塞,直到其他的线程往空的行列插入新的元素。一样,试图往已满的阻塞行列中增加新元素的线程一样也会被阻塞,直到其他的线程使行列重新变得余暇起来,如从行列中移除一个大要多个元素,大要完全清空行列.
2个附加操纵:
支持阻塞的插入方式:行列满时,行列会阻塞插入元素的线程,直到行列不满。
支持阻塞的移除方式:行列空时,获得元素的线程会期待行列变成非空。
基础数据结构 例:栈、队列、链表、数据、字典、树、等  热点新闻 1866130-20200214113302832-1587422212

怎样实现阻塞行列?固然是靠锁,可是应当怎样锁?一把锁能在not_empty,not_full,all_tasks_done三个条件之间同享。比如说,现在有线程A线程B,他们预备向行列put使命,行列的最大长度是5,线程A在put时,还没完事,线程B就起头put,行列就塞不下了,所以当线程A抢占到put权时应当加把锁,不让线程B对行列操纵。鬼畜区经常看到的计数君,在线程中也一样严重,每次put完unfinished要加一,get完unfinished要减一。
  1. import threading #引入线程 上锁import timefrom collections import deque # 导入行列class BlockQueue:def __init__(self, maxsize=0):'''一把锁三个条件(self.mutex,(self.not_full, self.not_empty, self.all_task_done)),最大长度与计数君(self.maxsize,self.unfinished)'''self.mutex = threading.Lock() # 线程上锁self.maxsize = maxsize self.not_full = threading.Condition(self.mutex)self.not_empty = threading.Condition(self.mutex)self.all_task_done = threading.Condition(self.mutex)self.unfinished = 0def task_done(self):'''每一次put完城市挪用一次task_done,而且挪用的次数不能比行列的元素多。计数君对应的方式,unfinished 0 时就不停wait()晓得unfinished=0跳出循环。'''with self.all_task_done:while self.unfinished:self.all_task_done.wait()def put(self, item, block=True, timeout=None):'''block=True不停阻塞直到有一个余暇的插槽可用,n秒内阻塞,假如在那个时候没不足暇的插槽,则会激发完全的很是。Block=False假如一个余暇的槽立即可用,则在行列上放置一个条目,否则就会激发完全的很是(在这类情况下,“超时”将被疏忽)。有空位,增加到行列没竣事的使命+1,他末端要叫醒not_empty.notify(),由于一路头是要在没满的情况下加锁,满了就期待not_full.wait,当put完今后就有工具了,每当一个item被增加到行列时,看护not_empty期待获得的线程会被看护。'''with self.not_full:if self.maxsize > 0:if not block:if self._size() >= self.maxsize:raise Exception("The BlockQueue is full")elif timeout is not None:self.not_full.wait()elif timeout < 0:raise Exception("The timeout period cannot be negative")else:endtime = time.time() + timeoutwhile self._size() >= self.maxsize:remaining = endtime - time.time()if remaining 4321,这样也太费劲了,类似冒泡排序了
  2. 应当是每次把n背面的数字放到前面来,1234n->1n234->21n34->321n4->4321n</p>那末接下来用 Python 实现
  3. 第一种方式[b] 循环方式[/b]
  4. 循环方式的脑筋是建立三个变量,别离指向当前结点,当前结点的前一个结点,新的head结点,从head起头,每次循环将相邻两个结点的偏向反转。当全部链表循环遍历过一遍以后,链表的偏向就被反转过来了。
  5. [align=center][img=753,118]http://www.45zhe.com/https://img2018.cnblogs.com/i-beta/1866130/202002/1866130-20200214155403734-780635454.png[/img][/align]
  6. [align=center][img=765,131]http://www.45zhe.com/https://img2018.cnblogs.com/i-beta/1866130/202002/1866130-20200214155421013-973865941.png[/img][/align]
  7. [align=center][img=705,137]http://www.45zhe.com/https://img2018.cnblogs.com/i-beta/1866130/202002/1866130-20200214155529199-421316607.png[/img][/align]
  8. [code]class ListNode:def __init__(self, x):self.val = xself.next = Nonedef reverse(head): # 循环的方式反转链表if head is None or head.next is None:return head# 界说反转的初始状态pre = Nonecur = headnewhead = headwhile cur:newhead = curtmp = cur.nextcur.next = prepre = curcur = tmpreturn newheadif __name__ == '__main__':head = ListNode(1) # 测试代码p1 = ListNode(2) # 建立链表1->2->3->4->None;p2 = ListNode(3)p3 = ListNode(4)head.next = p1p1.next = p2p2.next = p3p = reverse(head) # 输出链表 4->3->2->1->Nonewhile p:print(p.val)p = p.next
复制代码

第二种呢 就是 递归方式
按照递归的概念,我们只需要关注递归的基例条件,也就是递归的出口或递归的制止条件,以及长度为n的链表与长度为n-1的链表的关系即可
长度为n的链表的反转成果,只需要将长度为n-1的链表反转后,将链表末端指向None点窜成指向长度为n的链表的head,并让head指向None(大要说在链表与None之间增加长度为n的链表的head结点)
即反转长度为n的链表,首先反转n-1链表,然后再操纵反转好的链表与head结点的关系;至于n-1长度的链表怎样反转,只需要把它再拆分红node1和n-2的链表…
基础数据结构 例:栈、队列、链表、数据、字典、树、等  热点新闻 1866130-20200214155650270-698721515



基础数据结构 例:栈、队列、链表、数据、字典、树、等  热点新闻 1866130-20200214155720923-1159337290



基础数据结构 例:栈、队列、链表、数据、字典、树、等  热点新闻 1866130-20200214155757179-878862688



  1. class ListNode:def __init__(self, x):self.val = xself.next = Nonedef reverse(head, newhead): # 递归,head为原链表的头结点,newhead为反转后链表的头结点if head is None:returnif head.next is None:newhead = headelse:newhead = reverse(head.next, newhead)head.next.next = headhead.next = Nonereturn newheadif __name__ == '__main__':head = ListNode(1) # 测试代码p1 = ListNode(2) # 建立链表1->2->3->4->Nonep2 = ListNode(3)p3 = ListNode(4)head.next = p1p1.next = p2p2.next = p3newhead = Nonep = reverse(head, newhead) # 输出链表4->3->2->1->Nonewhile p:print(p.val)p = p.next
复制代码


数组
所谓数组,是有序的元素序列。若将有限个典范类似的变量的聚集命名,那末这个称号为数组名。组成数组的各个变量称为数组的份量,也称为数组的元素,偶然也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在步伐计划中,为了处置赏罚方便, 把具有类似典范的几多元素按无序的形式机关起来的一种形式。 这些无序排列的同类数据元素的聚集称为数组。
数组是用于贮存多个类似典范数据的聚集。
Python 没有内置对数组的支持,但可以利用 Python 列表取代。
一维数组
一维数组是最简单的数组,其逻辑结构是线性表。要利用一维数组,需经过界说、初始化和利用等进程。
在数组的声明格式里,“数据典范”是声明数组元素的数据典范,可所以java说话中尽情的数据典范,包含简单典范和结构典范。“数组名”是用来同一这些类似数据典范的称号,其命名法则和变量的命名法则类似。
数组声明以后,接下来即是要分派数组所需要的内存,这时必须用运算符new,其中“个数”是告诉编译器,所声明的数组要寄存几多个元素,所以new运算符是看护编译器按照括号里的个数,在内存平分派一块空间供该数组利用。利用new运算符为数组元素分派内存空间的方式称为静态分派方式。
二维数组
前面先容的数组只要一个下标,称为一维数组, 其数组元素也称为单下标变量。在现实题目中有很多量是二维的或多维的, 是以多维数组元素有多个下标, 以标识它在数组中的位置,所以也称为多下标变量。
二维数组在概念上是二维的,即是说其下标在两个偏向上变革, 下标变量在数组中的位置也处于一个平面当中, 而不是象一维数组只是一个向量。可是,现实的硬件存储器却是连续编址的, 也就是说存储器单元是按一维线性排列的。若何在一维存储器中寄存二维数组,可有两种方式:一种是按行排列, 即放完一行以后顺次放入第二行。另一种是按列排列, 即放完一列以后再顺次放入第二列。在C说话中,二维数组是按行排列的。在如上中,按行顺次寄存,先寄存a[0]行,再寄存a[1]行,末端寄存a[2]行。每行中有四个元素也是依次寄存。由于数组a说明为
int典范,该典范占两个字节的内存空间,所以每个元素均占据两个 字节(图中每一格为一字节)。
三维数组
三维数组,是指维数为三的数组结构。三维数组是最多见的多维数组,由于其可以用来描摹三维空间中的位置或状态而被普遍利用。
三维数组就是维度为三的数组,可以以为它表现对该数组存储的内容利用了三个自力参量去描摹,但更多的是以为该数组的下标是由三个差别的参量组成的。
数组这一概念严重用在编写步伐傍边,和数学中的向量、矩阵等概念有必定的差别,严重表现:在数组内的元素可所以尽情的类似数据典范,包含向量和矩阵。
对数组的拜候一样平常是经过下标举行的。在三维数组中,数组的下标是由三个数字组成的,经过这三个数字组成的下标对数组的内容举行拜候。
字符数组
用来寄存字符量的数组称为字符数组。
字符数组典范说明的形式与前面先容的数值数组类似。例如:char c[10]; 由于字符型和整型通用,也可以界说为int c[10]但这时每个数组元素占2个字节的内存单元。
字符数组也可以是二维或多维数组,例如:char c[5][10];即为二维字符数组

字典实现道理 NSDictionary
Python 中 dict 工具是表白白其是一个原始的Python数据典范,依照键值对的方式存储,其中文名字翻译为字典,望文生义其经过键名查找对应的值会有很高的服从,时候复杂度在常数级别O(1)
dict底层实现
在Python中,字典是经过 哈希表 实现的。也就是说,字典是一个数组,而数组的索引是键经过哈希函数处置赏罚后获得的。
哈希表
是按照关键码值(Key value)而间接举行拜候的数据结构。它经过把关键码值映照到表中一个位置来拜候记录,以加速查找的速度。
这个映照函数叫做散列函数,寄存记录的数组叫做散列表。
给定表M,存在函数f(key),对尽情给定的关键字值key,代入函数后若能获得包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表.
函数f(key)为哈希(Hash) 函数。
  1. >>> map(hash, (0, 1, 2, 3)) [0, 1, 2, 3] >>> map(hash, ("namea", "nameb", "namec", "named")) [-1658398457, -1658398460, -1658398459, -1658398462]
复制代码
哈希概念:哈希表的本质是一个数组,数组中每一个元素称为一个箱子(bin),箱子中寄存的是键值对。
哈希函数
哈希函数就是一个映照,是以哈希函数的设定很灵活,只要使得任何关键字由此所得的哈希函数值都落在表长答应的范围之内即可;
并不是全数的输入都只对应唯逐一个输出,也就是哈希函数不大要做成一个一对一的映照关系,其本质是一个多对一的映照,这也就引出了下面一个概念–辩说。
辩说
只要不是一对一的映照关系,辩说就一定会发生,照旧上面的极端例子,这时新加了一个员工号为2的员工,先不考虑我们的数组巨细已经定为2了,依照之前的哈希函数,工号为2的员工哈希值也是2,这与100000000001的员工一样了,这就是一个辩说,针对差别的治理思绪,提出三个差别的治理方式。
辩说治理方式
开放地址
开放地址的意义是除了哈希函数得出的地址可用,当出现辩说的时候其他的地址也一样可用,常见的开放地颔领袖的方式有线性探测再散列,二次探测再散列,这些方式都是在第一挑选被占用的情况下的治理方式。
再哈希法
这个方式是顺次次规定多个哈希函数,每次查询的时候顺次次挪用哈希函数,挪用到第一个为空的时候返回不存在,挪用到此键的时候返回其值。
链地址法
将全数关键字哈希值类似的记录都存在同一线性链表中,这样不需要占用其他的哈希地址,类似的哈希值在一条链表上,顺次次遍历便可以找到。
公共溢出区
其底子脑筋是:全数关键字和底子表中关键字为类似哈希值的记录,不管他们由哈希函数获得的哈希地址是什么,一旦发生辩说,都填入溢出表。
装填因子α
一样平常情况下,处置赏罚辩说方式类似的哈希表,其均匀查找长度依靠于哈希表的装填因子。哈希表的装填因子界说为表中填入的记录数和哈希表长度的壁纸,也就是标志着哈希表的装满水平。直旁观来,α越小,发生辩说的大要性就越小,反之越大。一样平常0.75比力合适,触及数学推导。
哈希存储进程
1.按照 key 盘算出它的哈希值 h。
2.假定箱子的个数为 n,那末这个键值对应当放在第 (h % n) 个箱子中。
3.假如该箱子中已经有了键值对,就利用开放寻址法大要拉链法治理辩说。
在利用拉链法治理哈希辩说时,每个箱子实在是一个链表,属于同一个箱子的全数键值对城市排列在链表中。哈希表另有一个严重的属性: 负载因子(load factor),它用来权衡哈希表的空/满水平,必定水平上也可以表现查询的服从,盘算公式为:负载因子 = 总键值对数 / 箱子个数负载因子越大,意味着哈希表越满,越轻易致使辩说,性能也就越低。是以,一样平常来说,当负载因子大于某个常数(大如果 1,大要 0.75 等)时,哈希表将自动扩容。哈希表在自动扩容时,一样平常会建立两倍于本来个数的箱子,是以即使 key 的哈希值安定,对箱子个数取余的成果也会发生改变,是以全数键值对的寄存位置都有大要发生改变,这个进程也称为重哈希(rehash)。哈希表的扩容并不总是可以大要有用治理负载因子过大的题目。假定全数 key 的哈希值都一样,那末即使扩容今后他们的位置也不会变革。固然负载因子会低落,但现实存储在每个箱子中的链表长度并不发生改变,是以也就不能进步哈希表的查询性能。基于以上总结,细致的朋友大要会发现哈希表的两个题目:
1.假如哈希表中本来箱子就比力多,扩容时需要重新哈希并移动数据,性能影响较大。
2.假如哈希函数计划不公道,哈希表在极端情况下会酿成线性表,性能极低。
Python中全数不成变的内置典范都是可哈希的。
可变典范(如列表,字典和聚集)就是不成哈希的,是以不能作为字典的键。


树是一种数据结构,它是由n(n>=1)个有限结点组成一个具有条理关系的聚集。把它叫做“树”是由于它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:
每个结点有零个或多个子结点;没有父结点的结点称为根结点;每一个非根结点有且只要一个父结点;除了根结点外,每个子结点可以分为多个不订交的子树;
树是一种严重的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系机关起来的结构,很象自然界中的树那样。
树的界说:
树是由边毗连的节点或极点的分层聚集。树不能有循环,而且只要节点和它的下降节点或子节点之间存在边。同一父级的两个子节点在它们之间不能有任何边。每个节点可以有一个父节点除非是顶部节点,也称为根节点。每棵树只能有一个根节点。每个节点可以有零个或多个子节点。鄙人面的图中,A是根节点,B、C和D是A的子节点。我们也可以说,A是B、C、D的父节点。B、C和D被称为兄弟姐妹,由于它们是来自同一父节点A。
基础数据结构 例:栈、队列、链表、数据、字典、树、等  热点新闻 1866130-20200214160431661-1233924337

树的品种:
无序树:树中尽情节点的子结点之间没有次第关系,这类树称为无序树,也称为自在树;
有序树:树中尽情节点的子结点之间有次第关系,这类树称为有序树;
二叉树:每个节点最多含有两个子树的树称为二叉树;
完全二叉树
满二叉树
哈夫曼树:带权途径最短的二叉树称为哈夫曼树或最优二叉树;
树的深度:
界说一棵树的根结点条理为1,其他节点的条理是其父结点条理加1。一棵树中全数结点的条理的最大值称为这棵树的深度。

二叉树、满二叉树、完全二叉树
二叉树是一种特此外树:它大要为空,在二叉树中每个节点最多有两个子节点,一样平常称为左子节点和右子节点(或左孩子和右孩子),而且二叉树的子树有左右之分,其次第不能尽情颠倒。
满二叉树: 在一棵二叉树中,假如全数分支结点都有左孩子和右孩子结点,而且叶子结点城市合在二叉树的最下层,这样的树叫做满二叉树
完全二叉树: 若二叉树中最多只要最下面两层的结点的度数可以小于2,而且最下面一层的叶子结点都是依次排列在该层最左侧的位置上,则称为完全二叉树
区分: 满二叉树是完全二叉树的惯例,由于满二叉树已经满了,而完全并不代表满。所以形状你也应当设想出来了吧,满指的是出了叶子节点外每个节点都有两个孩子,而完全的寄义则是末端一层没有满,并没有满。
基础数据结构 例:栈、队列、链表、数据、字典、树、等  热点新闻 1866130-20200214160606532-416086155

二叉树
在盘算机科学中,二叉树是每个结点最多有两个子树的树结构。凡是子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。
二叉树是递归界说的,其结点有左右子树之分,逻辑上二叉树有五种底子形状:
基础数据结构 例:栈、队列、链表、数据、字典、树、等  热点新闻 1866130-20200214160803283-541645383




(1)空二叉树——如图(a);
(2)只要一个根结点的二叉树——如图(b);
(3)只要左子树——如图(1);
(4)只要右子树——如图(3);
(5)完全二叉树——如图(3)。
留意:尽管二叉树与树有很多类似之处,但二叉树不是树的出格情况。 [1]

hash树
哈希树(或哈希特里)是一种持久性数据结构,可用于实现聚集和映照,旨在更换纯函数式编程中的哈希表。 在其底子形式中,哈希树在trie中存储其键的哈希值(被视为位串),其中现实键和(可选)值存储在trie的“终极”节点中
什么是质数 : 即只能被 1 和 自己 整除的数。
为什么用质数:由于N个差别的质数可以 ”分辨“ 的连续整数的数目,与这些质数的乘积类似。
也就是说倘使有21亿个数字的话,我们查找的哪怕是最底层的也仅仅需要盘算10次就能找到对应的数字。
所以hash树是一棵为查找而生的树。
例如:
从2起的连续质数,连续10个质数便可以分辨大约M(10) =23571113171923*29= 6464693230 个数,已经超出盘算机中常用整数(32bit)的表达范围。连续100个质数便可以分辨大约M(100) = 4.711930 乘以10的219次方。
而依照现在的CPU水平,100次取余的整数除法操纵几乎不算什么难事。在现实利用中,团体的操纵速度常常取决于节点将关键字装载内存的次数和时候。一样平常来说,装载的时候是由关键字的巨细和硬件来决议的;在类似典范关键字和类似硬件条件下,现实的团体操纵时候就严重取决于装载的次数。他们之间是一个成反比的关系。
AAA哈希树参考原址

B-tree/B+tree
Btree
Btree是一种多路自平衡搜索树,它类似普通的二叉树,可是Btree答应每个节点有更多的子节点。Btree表现图以下:
基础数据结构 例:栈、队列、链表、数据、字典、树、等  热点新闻 1866130-20200214160920838-1411620858

由上图可知 Btree 的一些特点:
全数键值散布在全部树中
任何关键字出现且只出现在一个节点中
搜索有大要在非叶子节点竣事
在关键字全集内做一次查找,性能逼近二分查找算法
B+tree
B+树是B树的变体,也是一种多路平衡查找树,B+树的表现图为:
基础数据结构 例:栈、队列、链表、数据、字典、树、等  热点新闻 1866130-20200214161001076-98493732




由图可看出B+tree的特点 同时也是 Btree 和 B+tree的区分
全数关键字存储在叶子节点,非叶子节点不存储实在的data
为全数叶子节点增加了一个链指针 只要一个
总结:在数据存储的索引结构上 Btree 更偏向于 纵向深度的存储数据 而 B+tree 更喜爱于 横向广度的存储数据。
AAAbtree 的 参考原址

免责声明:假如加害了您的权益,请联系站长,我们会实时删除侵权内容,感谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Copyright © 2006-2014 全椒百姓网-全椒知名**,发布及时新鲜的全椒新闻资讯 生活信息 版权所有 法律顾问:高律师 客服电话:0791-88289918
技术支持:迪恩网络科技公司  Powered by Discuz! X3.2
快速回复 返回顶部 返回列表