几种树形结构的总结

悠悠 2021-12-20 10:49 345阅读 0赞

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构包含三方面的内容：逻辑结构、存储结构和数据的运算。数据的逻辑结构与存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的的存储结构。逻辑结构（线性结构与非线性结构）存储结构（顺序存储、链式存储、索引存储、散列存储）

# 线性结构 #

数据元素之间存在一对一的关系

线性表 栈、队列、数组、串

，

线性表是具有相同数据类型的n个数据元素的有序序列

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70][]

顺序表：物理顺序（内存的分配顺序）逻辑顺序（元素占用内存的顺序）一致

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 1][]

如图 通过首地址和元素序号可以在O（1）时间内找到指定元素

但也因为俩顺序一致所以插入和删除的话都得往后移动元素

顺序表用数组实现 顺序表的特点即是数组的特点

链表 不要求物理顺序（内存的分配顺序）逻辑顺序（元素占用内存的顺序）一致 对链表的操作只要修改指针即可 。

由于链表的元素是离散的分布在存储空间中，不能直接找到表中的某个特定的结点，查找某个特点的结点时，需要从表头开始遍历，依次查找

以下是双链表的插入操作   LinkedList 采用双链表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 3][]

单链表与双链表各自特点

# 非线性结构（数据元素之间是一对多或者多对多的关系） #

树、图等

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 5][]

![20190628144743890.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 6][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 7][]

关于树的查找算法比较

二叉排序树

左节点的数据值小于根节点  右节点的数值大于根节点

平均查找长度是O（n）

![20190628144811855.png][]

平衡因子左右子树之差<=1

平衡二叉树 （特殊的二叉排序树）

平均查找长度是 因为他的平衡二叉树的高度小

平衡二叉树查询的时间复杂度是，查找速度最快和比较次数最少，既然性能已经如此优秀，但为什么实现索引是使用B-Tree而不是二叉查找树，关键因素是查询磁盘IO的次数。

数据库索引是存储在磁盘上，当表中的数据量比较大时，索引的大小也跟着增长，达到几个G甚至更多。当我们利用索引进行查询的时候，不可能把索引全部加载到内存中，只能逐一加载每个磁盘页，这里的磁盘页就对应索引树的节点。每个结点加载一次磁盘io，减少磁盘IO的次数就必须要压缩树的高度，让瘦高的树尽量变成矮胖的树，所以B-Tree就在这样伟大的时代背景下诞生了

[http://m.elecfans.com/article/662237.html][http_m.elecfans.com_article_662237.html]  解释

B树 又称多路平衡查找树

一棵m叉树

1.  树中每个结点至多有m棵子树
2.  若根节点不是终端结点，则至少有两颗子树
3.  除根结点外所有叶结点至少有m/2棵子树

B树图示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 8][]

每个结点的关键字个数1<=n<=m-1

B+树图示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 9][]

关键字 1<=n<=m

每个关键字不保存数据，只用来索引  就是说 5 28 65  可以通过P1 P2 P3  在子节点中找到 P1 P2 P3的地址就是5 28 65在子节点中的位置

B+树与B-tree树比较

1、Ｂ＋树中间节点没有卫星数据（索引元素所指向的数据记录），只有索引，而Ｂ树每个结点中的每个关键字都有卫星数据；这就意味着同样的大小的磁盘页可以容纳更多节点元素，在相同的数据量下，Ｂ＋树更加“矮胖”，ＩＯ操作更少

2、因为卫星数据的不同，导致查询过程也不同；Ｂ树的查找只需找到匹配元素即可，最好情况下查找到根节点，最坏情况下查找到叶子结点，所说性能很不稳定，而Ｂ＋树每次必须查找到叶子结点，性能稳定

哈希表存在一种函数映射关系

![2019062814484687.png][]

![20190628144850982.png][]

解决哈希冲突的方法 1：开放定址法 2 拉链法（hashmap采用）等

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 10][]

红黑树是一种弱平衡二叉树，平衡二叉树采用严格的旋转算法保证平衡，在修改删除元素的时候性能要略低，适用于读取数据频繁而修改较少的场景，红黑树适用于修改较多的场景，Hashmap被认为是修改操作要远多于查询操作的数据结构，因此使用的是红黑树

红黑树的形象介绍 [https://blog.csdn.net/qq\_36610462/article/details/83277524][https_blog.csdn.net_qq_36610462_article_details_83277524]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70]: /images/20211220/a0b78953a3da4ea8aa81dc6097f63762.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 1]: /images/20211220/f45a0105a6674adab01a727b9ee2d1f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 2]: /images/20211220/da8ac970dfa94b7a89841ec7b057033c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 3]: /images/20211220/fb8c8c701df6454b942777f722b63f9b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 4]: /images/20211220/1a83c67afc554ed5aea0b659285148bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 5]: /images/20211220/d1e216dbcff44155b5442f93fcf8be72.png
[20190628144743890.png]: /images/20211220/5b05a50e63734bc9bd4de4357f0b6a83.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 6]: /images/20211220/159923cef2344836b5c3f15678da7c55.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 7]: /images/20211220/a4727a32b19e497d98962ab6b05face8.png
[20190628144811855.png]: /images/20211220/f4ddb1423c344476a570c2a4a150841c.png
[http_m.elecfans.com_article_662237.html]: http://m.elecfans.com/article/662237.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 8]: /images/20211220/ae37882ee05c4bcbbfc1c539b379c9a0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 9]: /images/20211220/dce145febbd24545932383963747c4e7.png
[2019062814484687.png]: /images/20211220/ed0d70ccf7754c17ab0798b49537263f.png
[20190628144850982.png]: /images/20211220/f27be70829c14287a13aeff0a9301212.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzd2RfNTB4_size_16_color_FFFFFF_t_70 10]: /images/20211220/9b17d2a2e7cc4fc1b7f58792cb147501.png
[https_blog.csdn.net_qq_36610462_article_details_83277524]: https://blog.csdn.net/qq_36610462/article/details/83277524