Tree & Search
树以及树搜索算法
本节内容为自己整理,是 Graph & Search 的子集。示例中皆假设不同节点的值不同。
Binary Tree
Tree Representation
Tree Search
Depth First Search (DFS)
方法 1:使用递归
方法 2:使用栈迭代
Breadth First Search (BFS)
方法1:使用 list
方法2:使用 dequeue
Binary Search Tree (BST)
BST 是一种特殊的 Binary Tree,其中任意节点都满足:
左子树中所有节点的值都小于当前节点的值
右子树中所有节点的值都大于当前节点的值
BST 的一些特性罗列如下:
通过 in-order traversal 可以得到所有节点按 key 排序的结果
擅长做一些特殊查询
查询与某 key 大小最相近的元素(closest lower/greater elements)
区间查询(range queries)
如果是 Self-Balancing BST(Red-Black Tree, AVL Tree, Splay Tree)则所有操作的复杂度为
Search
Time complexity:
Insertion
Time complexity:
Deletion
删除的时候分三种情况考虑:
如果是 leaf node:直接删除
如果只有一个 child:交换两个节点的值,并把 child node 删了
如果有两个 children:找到 inorder 遍历的下一个 node,交换两个节点的值,并把下一个 node 删除
Time complexity:
Traversal
In-order traversal of BST always produces sorted output
we can construct a BST with only Preorder or Postorder or Level Order traversal.
number of unique BSTs with n distinct keys is Catalan Number
算法题集锦:
Breadth First/Level Order Search
Complete Tree
Dynamic Programming
Graph Search
Last updated