Introduction-to-Algorithms2

Before：风止于秋水，我止于你

Introduction to Algorithms 2 Binary Search Tree & Binary Search Sort

Base on ?

Runway Reservation System!!!(My favourite plane! We’re saved!)

Properties

Each node x in the binary tree has a key key(x).Nodes other than the root have a parent p(x).Nodes may have a left child left(x) and/or a right child right(x).
ps：ALL POINTERS!Unlike in the Heap.

Characteristics：for any node x, for all nodes y in the left subtree of x, key(y) ≤ key(x). For all nodes y in the right subtree of x key(y) ≥ key(x).

Insert

As the picture shows below🤓

Under the problem,we need to do the “Within K minutes Check” before inserting.If doesn’t follow,then stop the insertion.

Find Exists : find(val)

Follow left and right pointers until you find it or hit NIL.

Find the minimum element in a BST : findmin()

Just go left until you can’t.

Complexity

All the operations above have an O(h) time complexity.
ps: h is the height of BST

We may find a problem: somehow in a tricky (or abstract) way of insertion, the BST may turn to a List.So the complexity will be O(n),but we hope O(logn).😣😣😣

We’re gonna talk about it next time in the AVL Chapter😋😋😋
Balanced BSTs to the rescue in the next lecture!

Find the next larger element: next_larger(x)

IF right child is not NIL,return minimun(x -> right)
else y = parent(x)

while y not NIL and x = right(y)
    x =  y
    y = parent(y)
return y;

How many planes are scheduled to land at times ≤ t?

Algorithm:
1.Walk down tree to find desired time( find t pos )
2.Add in nodes that are smaller
3.Add in subtree sizes to the left( record the size of the subtrees)

附上早上手写的BST

（由于赶时间就没写类模板了，int型BST凑合看看吧😢）

//
// Created by JaneZ on 2025/3/2.
//
#ifndef BST_H
#define BST_H
#include <cstdio>

class BinarySearchTree {
private:
    struct treeNode {
        treeNode *parent;
        treeNode *left;
        treeNode *right;
        int count; //单个结点出现次数
        int size; //以该结点为根 的子树大小
        int value; //存储的值，这里以整数为例

        treeNode(treeNode *p = nullptr,treeNode *l = nullptr,treeNode *r = nullptr,int c = 1,int s = 1,int v = 0):
        parent(p),left(l),right(r),count(c),size(s),value(v){}
    };

    treeNode *root;

    treeNode *buildTree(treeNode *other) {
        if(other != nullptr) {
            treeNode *r = new treeNode(nullptr,nullptr,nullptr,other->count,other->size,other->value);
            r -> left = buildTree(other -> left);
            r -> right = buildTree(other -> right);
            return r;
        }else {
            return nullptr;
        }
    }

    void clear(treeNode *r) {
        if(r != nullptr) {
            if(r -> left != nullptr) {
                clear(r -> left);
            }
            if(r -> right != nullptr) {
                clear(r -> right);
            }
            delete r;
        }
    }
public:
    BinarySearchTree():root(nullptr){}

    BinarySearchTree(const BinarySearchTree &other) {
        root = buildTree(other.root);
    }

    ~BinarySearchTree() {
        clear(root);
    }

    treeNode *search(treeNode *r,int val) {
        if(r == nullptr) {
            return nullptr;
        }
        if(r -> value == val) {
            return r;
        }else if(val < r -> value){
            search(r -> left,val);
        }else if(val > r -> value) {
            search(r -> right,val);
        }
    }

    treeNode *insert(treeNode *r,int key) {
        if(r == nullptr) {
            r = new treeNode(nullptr,nullptr,nullptr,1,1,key);
        }else {
            if(r -> value == key) {
                r ->count ++;
            }else if(key < r -> value) {
                r = insert(r -> left,key);
            }else if(key > r -> value) {
                r = insert(r -> right,key);
            }
        }
        r -> size += r -> count;
        r -> size += r -> left ?root -> left -> size:0;
        r -> size += r -> right ?root -> right -> size:0;

        return r;
    }

    //返回新的根结点
    treeNode *remove(treeNode *r,int val) {
        if(r == nullptr) {
            return nullptr;
        }
        if(val < r -> value) {
            r -> left = remove(r -> left,val);
        }else if(val > r -> value) {
            r -> right = remove(r -> right,val);
        }else {
            if(r -> count > 1) {
                r -> count --;
            }else {
                if(r -> left == nullptr ) {
                    treeNode *tmp = r -> right;
                    delete r;
                    return tmp;
                }else if(r -> right == nullptr) {
                    treeNode *tmp = r -> left;
                    delete r;
                    return tmp;
                }else{
                    //用右子树的最小值作为新的根结点
                    treeNode *pos = findMin(r -> right);
                    r -> count = pos -> count;
                    r -> value = pos -> value;
                    pos -> count = 1;
                    r -> right = remove(r -> right,pos -> value);
                }
            }
        }
        r -> size += r -> count;
        r -> size += r -> left ?root -> left -> size:0;
        r -> size += r -> right ?root -> right -> size:0;

        return r;
    }

    treeNode *findMin(treeNode *r) {
        while(r -> left != nullptr) {
            r = r -> left;
        }
        return r;
    }

    //查找排名
    int queryRank(treeNode *r,int val) {
        if(r == nullptr) {
            return 0;
        }else if(r -> value == val) {
            if(r -> left == nullptr) {
                return 1;
            }else {
                return r -> left -> size + 1;
            }
        }else if(r -> value > val) {
            return queryRank(r -> left,val);
        }else {
            if(r -> left == nullptr) {
                return 1 + r -> count + queryRank(r -> right,val);
            }else {
                return r -> left -> size + r -> count + queryRank(r -> right,val);
            }
        }
    }

    //查找排名为第k名的树
    int queryKth(treeNode *r,int k) {
        if(r == nullptr) {
            return -1;
        }
        if(r -> left != nullptr) {
            if(r -> left -> size >= k) {
                return queryKth(r -> left ,k);
            }else if(r -> left -> size + r -> count >= k) {
                return r -> value;
            }
        }else {
            if(k == 1) {
                return r -> value;
            }
        }
        return queryKth(r -> right,k - (r -> left ?r -> left -> size : 0) - r -> count);
    }
};

#endif //BST_H

Conclusion

Still an easy one.Can’t wait to see AVL!
立下flag，争取这周搞定用AVL实现的map!😋