老狗啃骨头之数据结构-树和堆
source link: http://www.veiking.cn/blog/1014-page.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
老狗啃骨头之数据结构-树和堆_老狗啃骨头_Veiking百草园-知识点滴,日常分享
树在实际应用中非常广泛，较为具体的是，我们用到的Mysql数据库的索引，就是用B+树实现的；很多Hash结构，底层也是用到了红黑树。树是一种功能强大，但相对复杂一些的数据结构，在学习的过程中，可定是要多花些时间精力去深一下，在很多算法的优化上，也可以体会到树这种数据结构在实际运用中带来的乐趣
树是一种典型的非线性数据结构，是由有限节点组成的一个具有层次关系的集合。
树这个结构名字起得很形象，可以想象他是一个棵树，从根部开始，发枝散叶，形成一个枝繁叶茂的大树冠：
这个图上最上边的树根，这个节点，我们一般称之为根节点，向下层层发散，依次连接。相互连接的节点，离根节点层级近的，我们称之为父节点，层级远的，称之为子节点；最终的末梢，我们称之为叶子节点，很形象很形象。
可以总结，树有以下特点：根节点没有父节点，叶子节点没有子节点；每个非根节点有且只有一个父节点，每个节点有零或多个子节点。此外，在研究树的过程中，每个子节点发散的分支，我们称之为子树，子树之间不会相交。
树这种数据结构，在计算机的应用中非常广泛，在数据结构层面，树结构普遍用于算法的具体实现和优化。
在树结构的基础上，衍生出很多典型的特异结构，我们说比较典型的是二叉树，像平衡二叉树、红黑树、B-树等，都是由二叉树实现的。
在普通树的特性之上，二叉树结构具有以下特点：每个节点最多只有两个子节点；每个子节点都有顺序特征，我们称之为左右，左右不可调换。这个左右顺序，要强调下，哪怕是只有一个子节点，也是分左右的，且不可随意变更。
堆是树结构特性运用的一种特殊形式，它基于的这个逻辑树，且是二叉树，完全二叉树。
堆对节点值有特殊要求：子节点完全小于等于父节点的，被称为大顶堆；子节点完全大于等于父节点的，被称为小顶堆；反正堆不是大顶堆就是小顶堆，二选其一，如下图：
但从空间结构上，堆也不一定是树，比如这个大顶堆，根据这个完全二叉树的特性，我们就可以用数组结构进行逻辑映射，如下图：
然后我们用公式进行简单定义：大顶堆，即须满足arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]。
在计算时，数组这种基于下标的数据结构肯定是比树型数据结构要快的多的多。
堆的这种应用，既有树结构在算法上的特性，又可以利用数组这种线性结构的便捷快速特性，是一种非常典型的算法优化思路。
树在实际应用中非常广泛，较为具体的是，我们用到的Mysql数据库的索引，就是用B+树实现的；很多Hash结构，底层也是用到了红黑树。
树是一种功能强大，但相对复杂一些的数据结构，在学习的过程中，可定是要多花些时间精力去深一下，在很多算法的优化上，也可以体会到树这种数据结构在实际运用中带来的乐趣。
分享一个魔性争议：链表算不算是一种特殊的树。感兴趣的朋友可以底下跟小伙伴们讨论讨论，哈哈哈。
Recommend
-
8
插入排序，一般是说直接插入排序，是一种最直观最简单的排序算法。插入排序的原理是依次将未排序的数据元素插入已完成排序的有序数列，如此往复，最终完成所有数据的排序。在插入排序中，往前遍历的时候，遇到等值的元素就直接插入结...
-
4
简单选择排序是一种相对简单直观的基础排序算法，每一次都做简单选择，每一次都选出最大或最小。选择排序的核心思想就是：在遍历的过程中，每次都选数据样本中最小的数据，放在首位。看起来简单纯朴吧，从第一个元素开始，每次都取剩...
-
5
归并排序是一种非常典型的分治策略应用排序算法，简而概括：分而排之，合而并之。归并排序，据说是冯·诺伊曼在1945年首次提出。冯·诺伊曼，是现代计算机科学发展史上开天辟地的大佬之一，不单单是计算机领域，这哥们在整个数学、量子...
-
8
老狗啃骨头之数据结构-栈和队列_老狗啃骨头_Veiking百草园-知识点滴,日常分享 栈和队列也是比较常见的数据结构，它们是比较特殊的线性表。相对于数组和链表，栈和队列是一种更具特性的场景应用，栈和队列都可...
-
4
冒泡排序是交换排序，是一种简单直观的排序算法。冒泡的算法原理是逐次循环遍历，比较两个相邻的元素，将小的（或大的）往前调。这样，每一轮都能得到一个最小的（或最大的），剩下的重复这个操作，最后完成排序。这个算法的名字，每...
-
6
老狗啃骨头之算法-排序算法总结_老狗啃骨头_Veiking百草园-知识点滴,日常分享 关于排序的算法，还有很多种。还有一些排序算法的思想，在不同的使用场景下再结合其它的算法逻辑，又可以衍生出新的算法设计。比...
-
5
天地玄黄，宇宙洪荒……千年以前，南梁周大侍郎，用一夜白头给我们留下了包罗万象又朗朗上口的童谣，得以千年唱诵，这是古人原始纯真的智慧。但浩瀚如宇宙，细微如尘沙，世间如此繁杂，计算机是搞不懂的，计算机的一零世界努力模拟，也...
-
5
老狗啃骨头之数据结构-小说算法_老狗啃骨头_Veiking百草园-知识点滴,日常分享 一般说，随着数据结构复杂度和解决问题的复杂度的增长，时间复杂度也是随之增长的。在相同的资源条件下，空间复杂度和时间复杂度...
-
6
老狗啃骨头之数据结构-图和散列表_老狗啃骨头_Veiking百草园-知识点滴,日常分享 图也是典型的非线性数据结构，相较于树，更为复杂。线性表和树在逻辑结构上都是没有回路的，图就不一样了，图任意两个元素，都...
-
5
老狗啃骨头之数据结构-引言_老狗啃骨头_Veiking百草园-知识点滴,日常分享 我们存在的现实世界，是具象的，生活中的各种东西，是几十年反复加强的概念，锅碗瓢盆啤酒饮料矿泉水…但计算机是一个抽象世界，计算...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK