Notes for Lecture 15-16

Big-O

时间复杂度

算法的时间复杂度记做 T(n) = O(f(n))

f(n) - 算法的基本操作重复执行的次数是模块n的某一函数f(n),

随着模块n的增大，算法执行的时间增长率与f(n)的增长率成正比，所以f(n)越小，算法的时间复杂度越低，算法的效率越高。

  • 而判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高项）的阶数。

空间复杂度

算法的时空间复杂度记做 S(n) = O(f(n))

f(n) - 语句关于n所占存储空间的函数

算法实现所需的存储空间大小，n为问题规模

Trees

有向无环的链接结点结构

Terminology 术语

Binary trees

最多有两个孩子结点的树

递归定义

Empty(nullptr)

Or 一个根节点 该根节点包含

  • 数据成员
  • 左子树 可为空
  • 右子树 可为空

Application

Print

1
2
3
4
5
6
7
8
9
10
11
void printTree(Tree* root) {

    if(root!=nullptr) {

        cout<<root->data;
        printTree(root->left);
        printTree(root->right);

    }

}

Size 求二叉树的高度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int size(Tree* root) {

    if(root==nullptr) {

        return 0;

    }else {

        int left=size(root->left);
        int right=size(root->right);
        return left+right+1;

    }
}

Contain 是否包含对应结点

1
2
3
4
5
6
7
8
9
10
11
12
bool Contain(Tree* root,int value) {

    if(root!=nullptr){
        if(root->data==value) {
            return true;
        }
        if(Contain(root->left,value) || Contain(root->right,value)) {
                return true;
        }
        return false;
    }
}

Binary search trees - BST

Defination

二叉树

  • 左子树的值均比根节点小
  • 右子树的值均比根节点大

Traversal

pre-order 先序遍历 root -> 左子树 -> 右子树
in-order 中序遍历 左子树 -> root -> 右子树
post-order 后序遍历 左子树 -> 右子树 -> root

Application

Search in BST

Solution：

Empty 查找失败 Or

  • value小于当前结点data递归查找左子树
  • value大于当前结点data递归查找右子树
  • value等于当前结点data 返回true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool Contain(Tree* root,int value) {

    if(root!=nullptr){
        if(root->data==value) {

            return true;
        }else if(root->data>value) {

            Contain(Tree->left,value);
        }else {

            Contain(Tree->right,value);
        }
        return false;
    }
}

getMain/Max

Solution：

Max:为根节点右子树中最右下的结点的值 —右子树为空的结点

Min:为根节点左子树中最左下的结点的值 —左子树为空的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/getMain/Max 假设二分查找树非空

int getMain(Tree* root) {

    if(root->left==nullptr) {

        return root->data;
    }else {

        return getMain(root->left);
    }
}

int getMax(Tree* root) {

    if(root->right==nullptr) {

        return root->data;
    }else {

        return getMax(root->right);
    }
}

Add to a BST

Solution：

添加的结点为叶节点，二分搜索树中添加，比当前结点大，递归添加在其右子树中，否则，递归添加在左子树中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Add(Tree* &root,int value) {

    if(root==nullptr) {

        root=new Tree(value);
    }else {

        if(root->data<value) {

            Add(root->right,value);
        }else if(root->data>value) {

            Add(root->left,value);
        }
    }

}

Free the tree

后序递归delete

Removal

BST中删除指定值

Solution

找到指定值，并删除

  • 叶子结点

    删除该结点并更新父节点的指向为null
    delete node -- node = nullptr

  • 只有左子树

    需要暂存该节点的指针以便删除
    删除该节点并将父节点指向更新指向到第一个左孩子
    Tree* temp = node -- node = node->left -- delete temp

  • 只有右子树

  • 需要暂存该节点的指针以便删除
    删除该节点并将父节点指向更新指向到第一个右孩子
    Tree* temp = node -- node = node->right -- delete temp

  • full 满树

    使用左子树的最大结点值或者右子树的最小结点值替代当前结点值并递归删除子树最值结点
    node -> data = min/max -- removal(node->left,min) / removal(node->right,max)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
void Removal(Tree*& root,int value) {

    if(root!=nullptr)
    {
        if(root->data==value)
        {

            if(root->left==nullptr && root->right==nullptr)
            {
                delete root;
                root=nullptr;
            }
            else if(root->left==nullptr)
            {
                Tree* temp=root;

                root=root->right;

                delete temp;

            }
            else if(root->right==nullptr)
            {
                Tree* temp=root;

                root=root->left;

                delete temp;
            }
            else
            {
                int min=getMin(root->right);

                root->data=min;

                removal(root->right,min);
            }
        }

        else if(root->data>value)
        {

            Removal(Tree->left,value);
        }

        else
        {

            Removal(Tree->right,value);
        }
    }


}