【014-Week2】学习总结

[aiter]

学习笔记

本周重点：跳表、散列表、哈希算法、二叉树、红黑树

本周主要还是练习，课程学习相对少一些。

• 二叉树& 二叉搜索树
  • binary tree 本身很基础，使用也是最多的一种。本身限定为二叉，0、1、2个子节点都符合要求，运用于实际时，可能是更多的限定，比如：
    * 完全二叉树，那么只有1个子节点时，必须是左子字节。
    * leetcode上的求第二小的数字。限定子节点只能是0或2，不能是1
  • 为了避免二叉树的高度太高，退化成链表，这样就基本失去了树的特征，这又引出了：
    * 平衡二叉树，左右子树的高度不能“相差太多”
    * 完全二叉树，严格的平衡二叉树，左右高度相差最多为1。而且1个子节点时，必须是左子节点
    * 满二叉树，一种特殊的完全二叉树。所有的非叶子节点数都是2
    * 红黑树，比较难，后面再详细学习

      2               2           2           2
     / \             / \         / \         / \
    2   5           2   5       2    5      2    5
       / \             / \     / \  /      / \  / \ 
      5   7           5   7   5  7 6      5  7 6   7  
     /
    5
    二叉树        平衡二叉树   完全二叉树    满二叉树

都是二叉树，2、3、4都是平衡二叉树, 3、4都是完成二叉树。4是满二叉树

• 堆，就是一种完全二叉树。外加了一条，节点值大/小于左、右子节点值，分别就是大、小顶堆
• 二叉搜索树
  • 本身是有序的，左子节点的值小于节点值，右子节点值大于节点值
  • 基于上一条，中序遍历后，就是一个有序的序列
  • leetcode上《783. 二叉搜索树结点最小距离》,就是典型的应用。开始笔者使用了中序遍历成一个有序的双向链表序列，再遍历链表，求相邻数值的最小差值，这样时间复杂度比较高(中序遍历O(n)+遍历链表求差值O(n)???)。后面利用二叉搜索树，任何节点的中序遍历前序节点要么是左子节点，要么是左子树的最右节点。后序节点同样的道理。最小距离肯定出现在当前节点与前序、后序节点的差值中。

            4             4
          /  \          /  \
         2    6        2    6
       /  \            ^   / \
      1    3           |  5   8
           ^
           |

• 未完成：前、中、后序、层次遍历的实现
• top k frequent words

  使用了hash表+双向链表的实现

  • hash表，主要是O(1)时间复杂度定位对应的元素(也是双向链表中的节点)
  • 把当前节点，从链中移除
  • 再从链表头进行比较，选择插入的位置
  • 最后从链表头，输出top K的
• 利用队列实现广度优先搜索(BFS ，Breadth First Search)
• 利用栈实现深度优先搜索(DFS ，Depth First Search)
• 插入排序实现
• 归并排序实现
• 堆及堆排序
  上面几种实现本身没什么特别, 也是参考例子去实现的，有一点比较重要，以前都是学习理论，没有动手自己去实现。理解上还是不太深，自己实现一遍，加深了理解。比如：
  • 广度优先，没实现前，记得当时的一个图，一层层去遍历，也记得有个队列。自己实现是走迷宫，实际实现就是从当前点，依次查看当前点的右、下、左、上是否可走，可走的话，就把右、下、左、上的点，加入队尾，然后从队头中取一个元素作为当前点，再重复这个过程。利用队列的先进先出(FIFO)，就实现了"层层推进"的效果。
  • 而深度优先，则是采用栈的后进先出(LIFO)特性。实现了"一条路走到黑"的效果，只有真正没路可走了，而且还没走出迷宫，这时才能回到"岔路口"从另一条路再这样"一条路走到黑",每个岔路口，都是这样干的。这就是回溯（Backtrack)?

• 跳表：本周未涉及，周末有时间可以实现一下

[tommy1989]

你的排版真的很赞，可以用幕布app直接做成思维导图，并且还附了用字符画的数据结构，有极客风范，代码里面的注释也很详细。而且你对每个题目都进行了比较详细的推导梳理归纳,这些地方都是值得初学者学习的。

[HongChao6]

同意楼上的说法，希望楼主再接再厉，加油 ↖(^ω^)↗