数据结构:二叉查找树 - 木东驿站 - Powered by MoodBlog

CONTENT

数据结构:二叉查找树

二叉查找树

二叉树是节点最多只有两个子树的树状结构,这两个子树可以称为左子树和右子树。可是对于普通的二叉树,并没有足够的信息来提示我们左子树和右子树存储的是什么,我们没有办法进行高效的信息查找。为了提高查找效率,我们会把二叉树升级为二叉查找树(Binary Search Tree)。

二叉查找树是符合以下定义的二叉树:

1.节点左子树中全部的节点键值都比该节点要小。

2.节点右子树中全部的节点键值都比该节点要大。

3.没有重复键值

这样,我们在根据键值寻找一个节点的时候,是不是就可以有方向的进行寻找了?从根节点开始找,如果键值不等于目标键值,目标键值比当前节点的小,我们就跑去左子树继续寻找,反之去右子树。这样每次都能确定前进一层。这样查询效率将得到极大的提升。

1.jpg

节点结构定义

class BSTNode{
public:
    BSTNode(int d=0,BSTNode* l=0,BSTNode* r=0):data(d),left(l),right(r){};
    int data;
    BSTNode* left;
    BSTNode* right;

};

本文中的代码实现只为说明相关算法,并不能直接应用于工业设计,所以这里我就不用模板啦。节点数据皆为一个整数data。

需要一个数据节点,左子树指针left和右子树指针right。

二叉查找树结构定义

class BST{
public:
    BST(BSTNode* r=0):root(r){
        size = 0;
    }
    ~BST();
    enum dfstype{PRE=0,IN=1,POST=2};
    enum deletetype{MERGE=0,COPY=1};
    //插入
    void insert(int data);
    //查找
    bool find(int data) const;
    //层次遍历
    void bfs() const;
    //深搜遍历
    void dfs(BST::dfstype) const;
    //递归写法
    void predfs(BSTNode*) const;
    void indfs(BSTNode*) const;
    void postdfs(BSTNode*) const;
    //回溯写法
    void predfsNormal() const;
    void indfsNormal() const;
    void postdfsNormal() const;
    //计数写法
    void predfsCount() const;
    void indfsCount() const;
    void postdfsCount() const;
    void clearTime();
    //删除相关
    void deleteELement(int data,enum deletetype type);
    void mergeDelete(BSTNode*&);
    void copyDelete(BSTNode*&);
    //平衡树
    /*
    *中序遍历得到有序数组,然后根据数组重新构建树,效率较低
    */
    void balance();
    void balance(int data[],int first,int last);
    //DSW旋转算法
    void rightRotate(BSTNode* z,BSTNode* f,BSTNode* n);
    void leftRotate(BSTNode* z,BSTNode* f,BSTNode* n);
    void createList();
    void createPerfectTree();
    //AVL树

    //其它
    int getSize() const;
    void clear();//清空节点
    
private:
    BSTNode* root;
    int size;
};

插入算法

插入一个元素并不难,我们只要根据二叉查找树的定义一路走到底就可以了,在叶子节点上插入新节点。

void BST::insert(int data){
    BSTNode* newnode = new BSTNode(data);
    BSTNode* temp = root;
    BSTNode* pre = 0;
    while(temp!=0){
        pre = temp;
        if(temp->data>data){
            temp = temp->left;
        }else if(temp->data<data){
            temp = temp->right;
        }else{
            return;
        }
    }
    if(pre==0)
        root = newnode;
    else{
        if(pre->data>data){
            pre->left = newnode; 
        }else{
            pre->right = newnode;
        }
    }
    size++;
}


查找元素

对比每个节点的大小关系,小了去左边找,大了去右边找。如果走完最后一个叶子节点,那就说明该树中并没有要查找的元素。

bool BST::find(int data) const{
    BSTNode* temp = root;
    while(temp!=0)
    {
        if(temp->data==data)
            return true;
        else if(temp->data>data)
            temp = temp->left;
        else
            temp = temp->right;
    }
    return false;
}

树的遍历

遍历树的方法有深度优先遍历(DFS)和广度优先遍历(BFS)。

广度优先遍历很简单,我们利用队列一层层的访问就可以了。首先访问第一层节点,然后第二层节点……

void BST::bfs() const{
    BSTNode **queue = new BSTNode*[getSize()]();
    int index = 0;
    int l = 0;
    queue[l++] = root;
    while(index<l)
    {
        BSTNode* temp = queue[index];
        cout << temp->data << endl;
        if(temp->left!=0){
            queue[l++] = temp->left;
        }
            
        if(temp->right!=0)
            queue[l++] = temp->right;
        index++;
    }
    
    delete queue;
}

index小于1的时候,说明队列已经空了,我们已经访问完全部的节点。因为队列使用的是动态内存,在方法运行结束时并不会释放,所以我们要手动删除。

之所以申请动态内存来存放队列,是因为栈内存容量有限,当一棵树的节点过多时,栈内存无法存储过多数据。本文用到的栈(这里指结构,不是栈内存,要区分开)、队列均使用动态内存实现,下文对此不再进行说明。


深度优先遍历分为三种:先序遍历、中序遍历、后序遍历

三种遍历方式原理请自行查找,这里主要给出实现代码。对于符合定义的二叉查找树来说,中序遍历的结果恰好是有序的(有趣不有趣?),所以中序遍历应用最为广泛。

void BST::predfs(BSTNode* p) const{
    if(p!=0)
    {
        cout << p->data << endl;
        predfs(p->left);
        predfs(p->right);
    }
}
void BST::indfs(BSTNode* p) const{
    if(p!=0)
    {
        indfs(p->left);
        cout << p->data << endl;
        indfs(p->right);
    }
}
void BST::postdfs(BSTNode* p) const{
    if(p!=0)
    {
        postdfs(p->left);
        postdfs(p->right);
        cout << p->data << endl;
    }
}
//入口函数,根据参数选择不同的遍历方式
void BST::dfs(BST::dfstype type) const{
    if(type==0){
        predfs(root);
    }else if(type==1){
        indfs(root);
    }else if(type==2){
        postdfs(root);
    }
}

另外给出非递归的先序、中序遍历算法(为什么没后序?因为笨笨的博主写不出啊):

void BST::predfsNormal() const{
    if(root==0)
        return;
    BSTNode **stack = new BSTNode*[getSize()]();
    int index = -1;
    BSTNode *temp = root;
    while(temp||index>=0)
    {
        while(temp!=0){
            cout << temp->data << endl;
            stack[++index] = temp;
            temp = temp->left;
        }
        if(index>=0)
        {
            temp = stack[index]->right;
            index--;
        }
    }
    delete stack;
}
void BST::indfsNormal() const{
    if(root==0)
        return;
    BSTNode **stack = new BSTNode*[getSize()]();
    int index = -1;
    BSTNode *temp = root;
    while(temp||index>=0)
    {
        while(temp!=0){
            stack[++index] = temp;
            temp = temp->left;
        }
        if(index>=0)
        {
            cout << stack[index]->data << endl;
            temp = stack[index]->right;
            index--;
        }
    }
    delete stack;   
}

然而博主是那种写不出就放弃的人吗!所以使用访问计数器实现了更为简单的非递归遍历方法,需要用到两个栈,一个用来存储节点,另一个存储节点的访问次数,仅需向递归算法那样移动访问语句,就可以实现三种不同的深度遍历。

void BST::predfsCount() const{
    if(getSize()==0)
    {
        return;
    }
    BSTNode **stack = new BSTNode*[getSize()]();
    int *times = new int[getSize()]();
    int index = 0;
    stack[index] = root;
    while(index>=0)
    {
        times[index]++;
        if(times[index]==1)
        {
            cout << stack[index]->data << endl;
            if(stack[index]->left){
                stack[index+1] = stack[index]->left;
                index++;
            }
        }else if(times[index]==2){
            if(stack[index]->right){
                stack[index+1] = stack[index]->right;
                index++;
            }
        }else{
            times[index] = 0;
            index--;
        }
    }
    delete stack;
    delete times;
}
void BST::indfsCount() const{
    if(getSize()==0)
    {
        return;
    }
    BSTNode **stack = new BSTNode*[getSize()]();
    int *times = new int[getSize()]();
    int index = 0;
    stack[index] = root;
    while(index>=0)
    {
        times[index]++;
        if(times[index]==1){
            if(stack[index]->left){
                stack[index+1] = stack[index]->left;
                index++;
            }
        }else if(times[index]==2){
            cout << stack[index]->data << endl;
            if(stack[index]->right){
                stack[index+1] = stack[index]->right;
                index++;
            }            
        }else{
            times[index] = 0;
            index--;            
        }        
    } 
    delete stack;
    delete times;
}
void BST::postdfsCount() const{
    if(getSize()==0)
    {
        return;
    }
    BSTNode **stack = new BSTNode*[getSize()]();
    int *times = new int[getSize()]();
    int index = 0;
    stack[index] = root;
    while(index>=0)
    {
        times[index]++;
        if(times[index]==1){
            if(stack[index]->left){
                stack[index+1] = stack[index]->left;
                index++;
            }
        }else if(times[index]==2){
            if(stack[index]->right){
                stack[index+1] = stack[index]->right;
                index++;
            }            
        }else{
            cout << stack[index]->data << endl;
            times[index] = 0;
            index--;            
        }        
    }
    delete stack;
    delete times;  
}

先序遍历:第一次访问就输出,左节点入栈,第二次访问右节点入栈,第三次访问滚出栈。

中序遍历:第一次访问左节点入栈,第二次访问输出,右节点入栈,第三次访问输出并滚出。

后续遍历:第一次访问左节点入栈,第二次访问右节点入栈,第三次访问滚出。

删除节点

删除一个节点有点麻烦,分为以下情况:

1.如果是叶子节点,直接删除。

2.如果节点只有左子树或只有右子树,把左子树或右子树拼接到自己父亲节点上,然后干掉自己。

3.如果节点既有左子树也有右子树,就要用到两种算法:合并删除和复制删除。

void BST::deleteELement(int data,enum deletetype type){
    BSTNode *temp = root,*pre = 0;
    while(temp!=0){
        if(temp->data==data){
            break;
        }
        pre = temp;
        if(temp->data>data){
            temp = temp->left;
        }else{
            temp = temp->right;
        }
    }
    if(temp!=0){
        if(temp==root){
            if(type==BST::MERGE)
                mergeDelete(root);
            else
                copyDelete(root);
        }else if(pre->left==temp){
            if(type==BST::MERGE)
                mergeDelete(pre->left);
            else
                copyDelete(pre->left);
        }else{
            if(type==BST::MERGE)
                mergeDelete(pre->right);
            else
                copyDelete(pre->right);;
        }
    }
}

合并删除就是在左子树中找到最大的节点(就是最右边的节点,没有右子树),然后把右子树连接到这个左子树中的最大节点上,这样是不是被删除的节点就只有一个子树了?再把这个子树和要删除的节点的父节点连接上就可以了,最后干掉要删除的节点。这种方法会导致左子树越来越大,从而使二叉树不再平衡。

void BST::mergeDelete(BSTNode* &node){
    BSTNode* temp = node;
    if(node->left==0){
        node = node->right;
    }else if(node->right==0){
        node = node->left;
    }else{
        temp = temp->left;
        //find the biggest in the left node
        while(temp->right!=0)
            temp = temp->right;
        temp->right = node->right;
        temp = node;
        node = node->left;
    }
    delete temp;
}

复制删除就是把左子树中最大节点的值,赋给要删除的节点,然后删掉之前找到的那个最大节点。这样是不是无需变动树的结构?该方法不会增加树的高度,但也会导致不平衡(左子树越来越小)

void BST::copyDelete(BSTNode* &node){
 BSTNode *temp = node,*pre = node;
    if(node->left==0){
        node = node->right;
    }else if(node->right==0){
        node = node->left;
    }else{
        temp = temp->left;
        while(temp->right){
            pre = temp;
            temp = temp->right;
        }
        node->data = temp->data;
        if(pre==node)
            pre->left = temp->left;
        else
            pre->right = temp->left;
    
    }
    delete temp;
}

树的平衡

如果树的形状严重失衡,甚至变成了一条链,这时候查询效率就和普通链表(跳表吊打查找树好不好)无异了。我们需要对查找树进行平衡,这里提供两种办法。

第一种办法:利用中序遍历,得到一组有序的数据,清空当前全部节点,根据这组数据递归插入,每次插入的是当前区域中间的一个值,这样得到的新树是平衡的。

void BST::balance(){
    if(getSize()==0)
    {
        return;
    }
    int* arr = new int[getSize()]();
    int arrindex = 0;
    //以下代码和中序遍历相似,访问语句改为加入上面定义的数组
    BSTNode **stack = new BSTNode*[getSize()]();
    int *times = new int[getSize()]();
    int index = 0;
    stack[index] = root;
    while(index>=0)
    {
        times[index]++;
        if(times[index]==1){
            if(stack[index]->left){
                stack[index+1] = stack[index]->left;
                index++;
            }
        }else if(times[index]==2){
            arr[arrindex++] = stack[index]->data;
            if(stack[index]->right){
                stack[index+1] = stack[index]->right;
                index++;
            }            
        }else{
            times[index] = 0;
            index--;            
        }        
    } 
    delete stack;
    delete times;
    //根据数组建立新树
    balance(arr,0,arrindex-1);  
}
void BST::balance(int arr[],int first,int last){
    if(first<=last){
        int mid = (first+last)/2;
        insert(arr[mid]);
        balance(arr,first,mid-1);
        balance(arr,mid+1,last);
    }
}

第二种方法,叫什么DSW算法……参考《c++数据结构与算法》 反正我没看明白……就当翻译成代码吧

大概意思就是先生成一个主链,这个主链是不分叉的,而且是顺序的。然后不断旋转主链得到平衡树。

//生成主链
void BST::createList(){
    BSTNode* temp = root;
    BSTNode* pre = 0;
    while(temp!=0){
        if(temp->left){
            BSTNode* tmp = temp->left;
            rightRotate(pre,temp,temp->left);
            temp = tmp;
        }else{
            pre = temp;
            temp = temp->right;
        }
    }
}
//对主链进行旋转
void BST::createPerfectTree(){
    int n = getSize();
    int m = pow(2,(int)(log2(n+1)))-1;
    BSTNode* pre = 0;
    BSTNode* now = root;  
    BSTNode* next = now->right;

    for(int i=n-m;i>0;i--){
        leftRotate(pre,now,next);
        if(!next||!next->right)
            break;
        pre = next;
        now = pre->right;
        next = now->right;
    }
    while(m>1){
        m = m/2;
        pre = 0;
        now = root;  
        next = now->right;
        for(int i=0;i<m;i++){
            leftRotate(pre,now,next);
            if(!next||!next->right)
                break;
            pre = next;
            now = pre->right;
            next = now->right;
        }
        
    }
}

AVL树

上面说的平衡算法有点大题小做的意思,对于一个不平衡树,大部分情况是局部不平衡,上面这俩是直接推翻重做啊,太浪费了。于是AVL树出现了。

AVL树每一个节点都有一个平衡因子,平衡因子 = 右子树高度-左子树高度,所以平衡因子是1,0,-1的话,该节点及其子树是平衡的。不是这仨数怎么办呢?就需要进行旋转,将其转换为平衡树。注意,只需要这一次旋转就足够了,再上层的节点及其平衡因子无需改变。

当插入一个新元素时,向上层更新平衡因子,发现不平衡时就要进行旋转。删除节点极其麻烦,需要分情况讨论,本文不再进行描述,如有兴趣欢迎百度。

总结

二叉查找树的查询效率还是很高的,但要尽量使树平衡,如果完全偏向左边或完全偏向右边,就特么变成链表了,还会浪费很多空间。

个快快 2018年09月11日 天气 晴

REMARKS

© 2018 MoodBlog 0.2 个快快 作品 | 参考主题: mathilda by fuzzz. | 鲁ICP备16047814号