网站建设168,wordpress 站长统计,html制作个人简历代码带照片,抖音上的小程序怎么赚钱文章出处#xff1a;极客时间《数据结构和算法之美》-作者#xff1a;王争。该系列文章是本人的学习笔记。
1 树
1.1 概念
概念#xff1a;树、根、父节点、子节点、叶子节点。 几个度#xff1a;高度、深度、层。与实际生活中的这几个概念类比。 高度#xff1a;从下往…文章出处极客时间《数据结构和算法之美》-作者王争。该系列文章是本人的学习笔记。
1 树
1.1 概念
概念树、根、父节点、子节点、叶子节点。 几个度高度、深度、层。与实际生活中的这几个概念类比。 高度从下往上数从叶子往根从0开始。 深度从上往下看从根往叶子从0开始。 层数深度1
2 二叉树
2.1 定义
定义每个节点最多有两个子节点。 满二叉树除了叶子节点没有子节点其余每个节点都有2个子节点。 完全二叉树1 叶子节点在最下面两层2 最后一层的叶子节点都靠左排列3 除了最后一层其他层的节点达到最大个数。 二叉树的存储有两种方式。一种是链式存储,一个节点存储数据两个指针分别指向左右子节点。一种是顺序存储(数组存储)。根节点在下标为1的位置。左节点存储下标为2i2右节点存储下标为2i13。依次类推。下标为i的节点左子节点存储在下标为2i的位置右子节点存储在2i1的位置。
class Node{T value;Node leftChild;Node rightChild;
}如果一棵树是完全二叉树使用数组存储的话只有下标为0的位置是空的其余完全利用。而且不需要额外的指针更节约空间。这也是完全二叉树单独提出来的原因。
2.2 遍历
二叉树的遍历有前序遍历、中序遍历、后续遍历和层次遍历。前中后序遍历是指访问节点与其子节点的相对顺序。 前序遍历访问节点访问左子节点访问右子节点 中序遍历访问左子节点访问节点访问右子节点 后续遍历访问左子节点访问右子节点访问节点 前中后序遍历是一个递归过程。递归的重点是不是能写出递归公式。写递归公式的重点是能不能将要解决的问题A分解为子问题B、C、D假设B、C、D已经解决如何利用B、C、D的结果来解决问题A。
前序遍历递推公式
preOrder(r)print r-preOrder(r.leftChild)-preOrder(r.rightChild);
中序遍历递推公式
inOrder(r)inOrder(r.leftChild)-print r-inOrder(r.rightChild);
后序遍历递推公式
postOrder(r)postOrder(r.leftChild)-postOrder(r.rightChild)-print r;2.3思考题
给定一组数据1356910。可以构造出多少种不同的二叉树。 答案卡特兰数。
3 二叉查找树
定义二叉查找树中任意一个节点的左子树中的每一个节点都要求小于当前节点右子树的任意一个节点都要求大于当前节点。
3.1 二叉查找树的查找
当要查找一个数的时候从根节点开始。如果要查找的值等于根节点的值则返回。如果要查找的值大于根节点的值则在右子树递归查找。否则要从左子树递归查找。
3.2 二叉查找树的插入
插入操作与查找操作类似。从根节点开始。如果要插入的数据比节点数据大并且节点的右子树是空的则直接插入右子节点如果右子树不为空递归查找右子树寻找插入位置。 如果要插入的数据比节点数据小并且节点的左子树是空的则直接插入左子节点如果左子树不为空则递归查找左子树寻找插入位置。
3.3 二叉查找树的删除 二叉树的删除操作比较复杂需要分情况讨论。 规则1要删除的节点是一个叶子节点例如55。将其父节点指向该节点的引用置为空即可。 规则2要删除的节点有一个子节点例如13。将13父节点指向该节点的引用指向13的叶子节点。 规则3要删除的节点有两个子节点例如18。在18的右子树查找最小值19将18节点的value值改为最小值19删除节点19应用规则1或者规则2删除节点19。
二叉树的删除还有一种操作方法是将要删除的数据标记为删除状态并且真正删除。这样做会浪费部分空间但整体时间复杂度不会受影响且实现简单。
3.4其他操作
查找最大值 查找最小值 中序遍历得到一个顺序数组时间复杂度O(n)非常高效所以二叉查找树又被称为二叉排序树。
3.5 支持重复元素
如果要插入的元素有重复的该怎么处理 一种处理方法参考散列表的链式存储。树的每个节点存储数值的是一个链表遇到值相同的元素就依次添加到链表中。 一种处理方法是大于等于当前节点的元素都插入到右子树。当要查找的时候遇到相等的元素不停下来而是继续查找直到找到所有要查找的值值相同的元素。删除的时候也是同样。要删除每一个等于要删除值的节点。
3.6二叉查找树的时间复杂度分析 二叉查找树因为形态多样查找时间复杂度也不相同。例如图中第一棵树已经退化为链表时间复杂度O(n)。 第三棵树是一棵完全二叉树。无论查找、插入 删除时间复杂度与它的高度成正比。一棵 包含n个节点的完全二叉树高度是多少 完全二叉树每一层节点数量是1、2、4…2k−22^{k-2}2k−2假设有k层。最后一层节点数量在1到2k−12^{k-1}2k−1之间。假设最后一层节点数量是2k−12^{k-1}2k−1。那么124....2k−1n124....2^{k-1}n124....2k−1n则klog2(n1)klog_2(n1)klog2(n1)。假设最后一层节点数量是1那么124....2k−21n124....2^{k-2}1n124....2k−21nklog2n1klog_2n1klog2n1。k值的区间是[log2(n1),log2n1][log_2(n1),log_2n1][log2(n1),log2n1]。完全二叉树的层数小于等于log2n1log_2n1log2n1,则完全二叉树的高度小于等于log2nlog_2nlog2n。 所以在理想情况下完全二叉树的时间复杂度是O(logn)。
4 平衡二叉查找树-红黑树
红黑树目前我只了解概念关于从二三树到红黑树之后再学习。
