Trees¶

int binary_search(List Tbl, ElementType K){
    int left, right, mid;
    int NotFound = -1;
    left = 1;
    right = Tbl -> Length;

    while(left <= right){
        mid = (left + right) / 2;
        if(K < Tbl -> Element[mid])
            right = mid - 1;
        else if(K > Tbl -> Element[mid])
            left = mid + 1;
        else
            return mid;
    }
    return NotFound;
}

Time Complexity: \(O(log N)\)

Definitions¶

• 树（trees）
  • 包含1个根节点（root） \(r\)
  • 有0个或k个子树（subtrees） \(T_1,……,T_k\)

• 度（degree）

  • 对于 一个节点 ：它 所有子树的个数
  • 对于 一棵树 ：它 所有子树中最大的度 即为此树的度

• 父节点（parent）

  • 有子树的节点
• 孩子节点（children）
  • 父节点子树的根节点

• 兄弟节点（siblings）

  • 有共同父节点的孩子节点

• 叶子节点（leaf）

  • 度为0的节点（即没有子树）

• 路径（path）

  • 从 \(n_1\) 到 \(n_k\)，一个包含节点 \(n_1,n_2,……,n_k\) 唯一的序列，满足 \(n_i\) 是 \(n_{i+1}\) 的父节点（一路顺下来的意思）

• 路径长度（length）

  • 路径上边的条数

• 深度

  • 对于顶点 \(n_i\) ，从根节点出发到\(n_i\)的路径长度
  • \(depth(root) = 0\)

• 高度

  • 对于顶点 \(n_i\) ，从\(n_i\)到叶子节点的最长路径长度
  • \(height(leaf) = 0\)

根节点的高度 = 最深的叶子节点的深度

• 祖先 (ancestor)：从该节点到根节点的路径上所有的节点
• 后代 (descendant)：该节点所有子树的节点
• 内部节点 (internal vertices)：有孩子节点的顶点

Implementation¶

1. List Representation

   每个节点的空间大小取决于它有多少个子树实现起来麻烦

2. FirstChild-NextSibling Representation

   对于同一棵树表示不唯一，因为孩子的顺序可任意

Binary Trees¶

二叉树

Expression Trees / syntax trees¶

（表达式树/语法树）

• 中缀表达式 → 后缀表达式
• 类似后缀表达式求解

Tree 

Tree Traversals¶

树的遍历：

• 前序遍历（preorder traversals）

void preorder(tree_ptr tree){
    if (tree){
        visit(tree);

        for (each child C of tree)
            preorder(C);
    }
}

• 后序遍历（postorder traversals）

void postorder(tree_ptr tree){
    if(tree){
        for(each child C of tree)
            postorder(C);
        visit(tree);
    }
}

• 层序遍历（levelorder traversals）

• 中序遍历（inorder traversals）

Threaded Binary Trees¶

线索二叉树

一些特例 - 完全二叉树 (complete binary trees)

• 歪斜二叉树 (skewed binary trees)

BST Tree¶

Implementations⚓︎¶

• Find
  • FindMin
  • FindMax
• Insert
• Delete

AVL Tree¶

Segment Tree¶

线段树（segment tree）-- 区间树（interval tree）

leading: 频繁区间查询 - 区间查询 Range Query 更快 - 单点修改 Point Update 也不能太慢

把一个大区间不断二分成小区间，每个节点保存一个区间的信息。

线段树 = 区间递归二分 + 节点保存区间答案 + 查询/更新时只走必要分支

结构

                    [0,4] = 25
                    /            \
            [0,2] = 14        [3,4] = 11
            /       \          /       \
    [0,1] = 9    [2]=5    [3]=8    [4]=3
        /    \
    [0]=7  [1]=2

• 求和线段树 （sum segment tree）
• 最小值线段树（min segment tree）
• 最大值线段树（max segment tree）

区间最小值查询 / Range Minimum Query

操作集¶

Build 建树 Query 区间查询 Update 单点更新 PushDown 懒惰标记下推 RangeUpdate 区间更新

• 建树
  • 时间复杂度 \(O(N)\)
  • 空间复杂度 \(O(N)\)

    如果有 \(N\) 个叶节点，则线段树的总节点数为 \(2N - 1\)，因此空间复杂度为 \(O(2N - 1)\)，简化后为 \(O(N)\)。

• 区间查询
  • 时间复杂度 \(O(log N)\)
  • 空间复杂度 \(O(1)\)
  • No Overlap
  • Total Overlap
  • Partial Overlap
  • Unvisited

• 单点更新
  • 时间复杂度 \(O(log N)\)
  • 空间复杂度 \(O(1)\)

单点更新只影响 从根到目标叶节点的一条路径，不会影响整棵树

HW4 -- tree¶

True-False Questions¶

1. It is always possible to represent a tree by a one-dimensional integer array.

2. There exists a binary tree with 2016 nodes in total, and with 16 nodes having only one child.

Multiple-Choice Questions¶

1. Given a tree of degree 3. Suppose that there are 3 nodes of degree 2 and 2 nodes of degree 3. Then the number of leaf nodes must be ____.

2. If a general tree \(T\) is converted into a binary tree \(BT\), then which of the following \(BT\) traversals gives the same sequence as that of the post-order traversal of \(T\)?

3. Given the shape of a binary tree shown by the figure below. If its inorder traversal sequence is { E, A, D, B, F, H, C, G }, then the node on the same level of C must be:

   

4. Among the following threaded binary trees (the threads are represented by dotted curves), which one is the postorder threaded tree?

HW5 -- binary search tree¶

True-False Questions¶

1. In a binary search tree, the keys on the same level from left to right must be in sorted (non-decreasing) order.

2. In a binary search tree which contains several integer keys including 4, 5, and 6, if 4 and 6 are on the same level, then 5 must be their parent.

Multiple-Choice Questions¶

1. Given a binary search tree as shown in the following figure. Which of the following relationships is correct with respect to the given tree?

2. Given the structure of a binary search tree (as shown in the figure), which one of the following insertion sequences is impossible?

3. Given a binary search tree with its preorder traversal sequence { 8, 2, 15, 10, 12, 21 }. If 8 is deleted from the tree, which one of the following statements is FALSE?

   • A.One possible preorder traversal sequence of the resulting tree may be { 2, 15, 10, 12, 21 }

   • B.One possible preorder traversal sequence of the resulting tree may be { 10, 2, 15, 12, 21 }

   • C.One possible preorder traversal sequence of the resulting tree may be { 15, 10, 2, 12, 21 }

   • D.It is possible that the new root may have 2 children

4. Insert {5, 2, 7, 3, 4, 1, 6} one by one into an initially empty binary search tree. The postorder traversal sequence of the resulting tree is:

   • A.1, 2, 3, 4, 6, 7, 5

   • B.1, 4, 2, 6, 3, 7, 5

   • C.1, 4, 3, 2, 6, 7, 5

   • D.5, 4, 3, 7, 6, 2, 1

5. Among the following binary trees, which one can possibly be the decision tree (the external nodes are excluded) for binary search?

6. For a binary search tree, in which order of traversal that we can obtain a non-decreasing sequence?

   • A.preorder traversal

   • B.postorder traversal

   • C.inorder traversal

   • D.level-order traversal

HW7 -- segment tree¶

True-False Questions¶

1. A segment tree can be used to find the greatest common divisor (GCD) of any index range.

2. In Union/Find algorithm, if Unions are done by size, the depth of any node must be no more than \(N/2\), but not \(O(logN)\).

Multiple-Choice Questions¶

1. The array representation of a disjoint set containing numbers 0 to 8 is given by { 1, -4, 1, 1, -3, 4, 4, 8, -2 }. Then to union the two sets which contain 6 and 8 (with union-by-size), the index of the resulting root and the value stored at the root are:

2. A.1 and -6

3. B.4 and -5

4. C.8 and -5

5. D.8 and -6

6. A relation R is defined on a set S. If for every element e in S, "e R e" is always true, then R is said to be __ over S.

7. A.consistent

8. B.symmetric

9. C.transitive

10. D.reflexive

11. Let T be a tree created by union-by-size with N nodes, then the height of T can be .

12. A.at most \(log_2(N)+1\)

13. B.at least \(log_2(N)+1\)

14. C.as large as \(N\)

15. D.anything that is greater than 1

16. What is a segment tree primarily used for?

17. A.Sorting elements

18. B.Finding minimum/maximum in a range

19. C.Finding the sum of a given set of integers

20. D.Finding a given string from a set of strings

SetType Find ( ElementType X, DisjSet S )
{   
    ElementType root, trail, lead;

    for ( root = X; S[root] > 0; @@ ) ;  
    for ( trail = X; trail != root; trail = lead ) {
        lead = S[trail] ;   
        @@;   
    } 
    return root;
}