二分搜索树

性质:
每个节点的键值大于左孩子;
每个节点的键值小于右孩子;
以左右孩子为根的子树仍为二分搜索树
注意:不一定是完全二叉树
查找时间复杂度O(log(n)) ,其实查找所需的最大次数等同于二叉查找树的高度

二分搜索树c++代码实现（递归实现):

#include <iostream>
#include <vector>
#include <string>
#include "SequenceST.h"
#include "FileOps.h"

using namespace std;

template <typename Key, typename Value>
class BST{

private:
    struct Node{
        Key key;
        Value value;
        Node *left;
        Node *right;

        Node(Key key, Value value){
            this->key = key;
            this->value = value;
            this->left = this->right = NULL;
        }
    };

    Node *root;
    int count;

public:
    BST(){
        root = NULL;
        count = 0;
    }
    ~BST(){
        // TODO: ~BST()
    }

    int size(){
        return count;
    }

    bool isEmpty(){
        return count == 0;
    }

    void insert(Key key, Value value){
        root = insert(root, key, value);
    }

    bool contain(Key key){
        return contain(root, key);
    }

    Value* search(Key key){
        return search( root , key );
    }

private:
    // 向以node为根的二叉搜索树中,插入节点(key, value)
    // 返回插入新节点后的二叉搜索树的根
    Node* insert(Node *node, Key key, Value value){

        if( node == NULL ){
            count ++;
            return new Node(key, value);
        }

        if( key == node->key )
            node->value = value;
        else if( key < node->key )
            node->left = insert( node->left , key, value);
        else    // key > node->key
            node->right = insert( node->right, key, value);

        return node;
    }

    // 查看以node为根的二叉搜索树中是否包含键值为key的节点
    bool contain(Node* node, Key key){

        if( node == NULL )
            return false;

        if( key == node->key )
            return true;
        else if( key < node->key )
            return contain( node->left , key );
        else // key > node->key
            return contain( node->right , key );
    }

    // 在以node为根的二叉搜索树中查找key所对应的value
    Value* search(Node* node, Key key){

        if( node == NULL )
            return NULL;

        if( key == node->key )
            return &(node->value);
        else if( key < node->key )
            return search( node->left , key );
        else // key > node->key
            return search( node->right, key );
    }
};

链表

性质:
链表是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的
每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
查找时间复杂度O(n)
插入时间复杂度O(1)

链表c++代码实现

#include <iostream>
#include <cassert>

using namespace std;


template<typename Key, typename Value>
class SequenceST{
private:
    struct Node{
        Key key;
        Value value;
        Node *next;

        Node(Key key, Value value){
            this->key = key;
            this->value = value;
            this->next = NULL;
        }
    };

    Node* head;
    int count;

public:
    SequenceST(){
        head = NULL;
        count = 0;
    }
    ~SequenceST(){
        while( head != NULL){
            Node *node = head;
            head = head->next;
            delete node;
            count --;
        }

        assert( head == NULL && count == 0 );
    }

    int size(){
        return count;
    }

    bool isEmpty(){
        return count == 0;
    };
    //从链表的头部插入
    void insert(Key key, Value value){
        Node *node = head;
        while( node != NULL ){
            if( key == node->key ){
                node->value = value;
                return;
            }
            node = node->next;
        }

        Node *newNode = new Node(key, value);
        newNode->next = head;
        head = newNode;
        count ++;
    }
    //判断链表中是否包含某个键
    bool contain(Key key){

        Node *node = head;
        while( node != NULL ){
            if( key == node->key ){
                return true;
            }
            node = node->next;
        }

        return false;
    }
   //读出链表中键对应的值
    Value* search(Key key){

        Node *node = head;
        while( node != NULL ){
            if( key == node->key ){
                return &(node->value);
            }
            node = node->next;
        }

        return NULL;
    }

    void remove(Key key){

        if( key == head->key ){
            Node* delNode = head;
            head = head->next;
            delete delNode;
            count--;
            return;
        }

        Node *node = head;
        while( node->next != NULL && node->next->key != key )
            node = node->next;

        if( node->next != NULL ){
            Node* delNode = node->next;
            node->next = delNode->next;
            delete delNode;
            count --;
            return;
        }
    }
};

测试代码:

int main() {

    string filename = "bible.txt";
    vector<string> words;
    if( FileOps::readFile(filename, words) ) {

        cout << "There are totally " << words.size() << " words in " << filename << endl;

        cout << endl;


        // test BST
        time_t startTime = clock();
        BST<string, int> bst = BST<string, int>();
        for (vector<string>::iterator iter = words.begin(); iter != words.end(); iter++) {
            int *res = bst.search(*iter);
            if (res == NULL)
                bst.insert(*iter, 1);
            else
                (*res)++;
        }

        cout << "'god' : " << *bst.search("god") << endl;
        time_t endTime = clock();
        cout << "BST , time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " s." << endl;

        cout << endl;


        // test SST
        startTime = clock();
        SequenceST<string, int> sst = SequenceST<string, int>();
        for (vector<string>::iterator iter = words.begin(); iter != words.end(); iter++) {
            int *res = sst.search(*iter);
            if (res == NULL)
                sst.insert(*iter, 1);
            else
                (*res)++;
        }

        cout << "'god' : " << *sst.search("god") << endl;

        endTime = clock();
        cout << "SST , time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " s." << endl;

    }

    return 0;
}

最后结果:

'god' : 2101
BST ,time : 0.599448 s.
'god' : 2301
SST ,time: 55.1001 s.