二叉查找树

二叉查找树

分类： 数据结构 2012-10-11 07:25 208人阅读 评论(0) 收藏 举报

1.定义

二叉排序树（Binary Sort Tree）又称二叉查找树。 它或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；

2.节点结构

2.1 拥有key值（排序）

2.2 拥有value值（实用）

2.3左子树指针

2.4右子树指针

2.5父亲节点指针（删除节点需要处理节点上界）

 

3.优/缺点

假设一个BST是平衡的，那么CRUD一个元素的时间复杂度为 O(logN) 即为树高。那么插入/删除频繁(很多动态数据)的处理性能会很好。

但是插入与删除操作容易让一棵树不平衡：

插入：如果插入数据有序性较好，产生的树将趋近于链表。 如 1,2,3,4,5  全部只有右节点。 只有当插入很均匀的时候可能出现平衡（程序员不可控，后续文章会有平衡树）

删除：二叉查找树一般的删除策略（左右子节点都有的情况）是替换左子树最大节点，或者右子树最小节点。长期使用一种方式也会让树趋近链表。

 

4处理过程

插入：二分处理过程。相等则更新节点/不处理；小则往左走，大则往右走，直到发现一个空节点，创建并添加。添加一对指针关系：父亲指向新节点/新节点指向父亲。

查找：二分处理过程。

查找最大值：二分处理过程，不过一直往右走到底即可。

删除：分情况：1.叶节点删除，只考虑父节点对应子指针。2.只有左/右子树的节点删除，把子树往上“提”一层，类似于双向链表删除，考虑下删除节 点是父亲的左节点还是右节点。3.左右子树都存在，找到左子树最大值/右子树最小值，与删除节点进行k,v交换，之后删除找到的节点，即1,2的情况。

 

5.一个粗略的实现

[cpp] view plaincopy

#include <iostream>
using namespace std;


/////////////////////////////////////////////////////////////////////
//二叉查找树(key,value都是int)
//性质：
//1.按key有序二叉树，如一个节点左小右大（等）==》中序遍历可以顺序输出元素
//2.
struct BST_DATA{
    int key;
    int value;
};

class BinarySearchTreeNode{
public:
    BinarySearchTreeNode(BST_DATA newdata)
    {
        key=newdata.key;
        value=newdata.value;
        left=NULL;
        right=NULL;
        parent=NULL;
    }
public:
    int key;
    int value;
    BinarySearchTreeNode * left;
    BinarySearchTreeNode * right;
    BinarySearchTreeNode * parent;
};

////////////////////////////////////////-----------普通插入，O(logN),树高即可---------------------///////////////////////////////////
bool binarySearchTreeInsert(BinarySearchTreeNode ** ppNode, BST_DATA newdata,BinarySearchTreeNode *pParentNode)
{
    if(NULL == *ppNode){
        *ppNode= new BinarySearchTreeNode(newdata);
        (*ppNode)->parent=pParentNode;
        return true;
    }

    if((newdata.key == (*ppNode)->key))//相等，不处理或更新，这里选择更新
    {
        (*ppNode)->value=newdata.value;
        return true;
    }
    if((newdata.key < (*ppNode)->key))
    {
        return binarySearchTreeInsert( & ((*ppNode)->left), newdata, *ppNode );
    }
    else
    {
        return  binarySearchTreeInsert( & ((*ppNode)->right), newdata, *ppNode );
    }
}
//处理边界+插入
bool insert(BinarySearchTreeNode ** ppNode, BST_DATA newdata){
    //结构体不存在
    if(NULL==ppNode){return false;}
    //新节点作为根
    if(NULL==*ppNode){
        *ppNode= new BinarySearchTreeNode(newdata);
        return true;
    }
    //插入
    return binarySearchTreeInsert(ppNode, newdata,NULL);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////-----------遍历，复杂度O(N),N为节点数--/////////////////////////////////
///////////////-----------前序遍历---------------------///////////////////////
void pre_scan(BinarySearchTreeNode ** ppNode){
    if(NULL!=ppNode && NULL !=*ppNode){
    //  printf("k%d-v%d#",(*ppNode)->key,(*ppNode)->value);
        printf("%d,",(*ppNode)->key);
        pre_scan(&((*ppNode)->left));
        pre_scan(&((*ppNode)->right));
    }
}
///////////////-----------中序遍历（按key顺序）---------------------///////////////////////
void in_scan(BinarySearchTreeNode ** ppNode){
    if(NULL!=ppNode && NULL !=*ppNode){
        in_scan(&((*ppNode)->left));
    //  printf("k%d-v%d#",(*ppNode)->key,(*ppNode)->value);
        printf("%d,",(*ppNode)->key);
        in_scan(&((*ppNode)->right));
    }
}


////////////////////////////////////////-----------查找(logN)---------------------///////////////////////////////////
//非递归
//根据data 查找
BinarySearchTreeNode * find_node(BinarySearchTreeNode ** ppNode,BST_DATA newdata)
{
    BinarySearchTreeNode * pHead = * ppNode;
    while(pHead!=NULL){
        if(pHead->key==newdata.key)
        {
            return pHead;
        }else if(pHead->key>newdata.key)
        {
            pHead=pHead->left;
        }else
        {
            pHead=pHead->right;
        }
    }
    return NULL;//未找到
}

//查找最大节点
BinarySearchTreeNode * find_max_node(BinarySearchTreeNode ** ppNode)
{
    BinarySearchTreeNode * pHead = * ppNode;
    while(pHead->right!=NULL){pHead=pHead->right;}
    return pHead;
}


///////////////-----------删除所有O(N)---------------------///////////////////////
void delete_tree(BinarySearchTreeNode ** ppNode)
{
    if(NULL==ppNode || NULL==*ppNode){return ;}
    delete_tree(&((* ppNode)->left));
    delete_tree(&((* ppNode)->right));
    delete (*ppNode);
}
///////////////-----------删除一个****难点---------------------///////////////////////
//1.叶子节点删除
//2.只有左子树，或者右子树，上移
//3.左子树，右子树都有***，替换左子树最大值，或者右子树最小值（问题，总是选择左树最大值，会让左树趋近直线，导致不平衡）

bool delete_node_from_tree(BinarySearchTreeNode** ppNode, BST_DATA data)
{

    if(NULL == ppNode || NULL == *ppNode) {return false;}//边界

    BinarySearchTreeNode *deleteNode = * ppNode;
    BinarySearchTreeNode * l_maxNode;

    //确定删除节点
    if(deleteNode->key==data.key)
    {

        //1.左右都有，换左子树最大值
        if(deleteNode->left!=NULL && deleteNode->right!=NULL)
        {
                l_maxNode = find_max_node(&(deleteNode->left));
                //////////////////////////////交换 a=a+b; b=a-b; a=a-b;
                l_maxNode->key = l_maxNode->key + deleteNode->key;
                deleteNode->key = l_maxNode->key - deleteNode->key;
                l_maxNode->key = l_maxNode->key - deleteNode->key;
                l_maxNode->value = l_maxNode->value + deleteNode->value;
                deleteNode->value = l_maxNode->value - deleteNode->value;
                l_maxNode->value = l_maxNode->value - deleteNode->value;
                //////////////////////////////处理删除节点下面
                if(l_maxNode->parent->right==l_maxNode){
                        l_maxNode->parent->right=l_maxNode->left;
                }else{//max父节点是根
                        l_maxNode->parent->left=l_maxNode->left;
                }
                //////////////////////////////处理删除节点上面
                if (NULL != l_maxNode->left) {
                    l_maxNode->left->parent = l_maxNode->parent;
                }

                delete l_maxNode;
        }
        else{
            //2.只有左或右，上移
            //2.1只有左子树
            if(deleteNode->left!=NULL)
            {
                if(deleteNode->parent!=NULL)//不是根节点
                {
                    //////////////////////////////处理删除节点上面
                    if(deleteNode->parent->left==deleteNode)//是父亲的左儿子
                    {
                        deleteNode->parent->left=deleteNode->left;
                    }else//右儿子
                    {
                        deleteNode->parent->right=deleteNode->left;
                    }
                }
                //////////////////////////////处理删除节点下面
                deleteNode->left->parent = deleteNode->parent;
            }
            //2.2只有右子树
            else if(deleteNode->right!=NULL)
            {
                if(deleteNode->parent!=NULL)
                {
                    //////////////////////////////处理删除节点上面
                    if(deleteNode->parent->left==deleteNode)
                    {
                        deleteNode->parent->left=deleteNode->right;
                    }else
                    {
                        deleteNode->parent->right=deleteNode->right;
                    }
                }
                //////////////////////////////处理删除节点下面
                deleteNode->right->parent = deleteNode->parent;
            }
            //3.左右都无
            else
            {
                if(deleteNode->parent!=NULL)//不是根节点
                {
                    //////////////////////////////处理删除节点上面
                    if(deleteNode->parent->left==deleteNode)
                    {
                        deleteNode->parent->left=NULL;
                    }else
                    {
                        deleteNode->parent->right=NULL;
                    }
                }
            }

            delete deleteNode;
        }
        return true;
    }
    else if(deleteNode->key<data.key)
    {
        return delete_node_from_tree(&((*ppNode)->right),  data);
    }
    else
    {
        return delete_node_from_tree(&((*ppNode)->left),  data);
    }

    return true;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////

int main(void)
{
    int key_array[10] = {12,5,18,2,15,9,19,13,17,3}; //插入顺序随即（手动）
    int value_array[10]={ 1,2, 3,4, 5,6, 7, 8, 9,10};
    BST_DATA bst_data_array[10]={0};
    for(int i=0;i<10;i++)
    {
        bst_data_array[i].key=key_array[i];
        bst_data_array[i].value=value_array[i];
    }

    BinarySearchTreeNode * ppNode=NULL;
    for(int j=0;j<10;j++){
        insert(&ppNode, bst_data_array[j]);
    }


    pre_scan(&ppNode);
    printf("\n");
    in_scan(&ppNode);
    printf("\n");

    BST_DATA td;
    td.key=1;
    td.value=2;

    /*
    //测试find_node
    BinarySearchTreeNode * node =find_node(&ppNode,bst_data_array[3]);
    if(NULL!=node){printf("\nx %d\n ",node->key);}
    in_scan(&ppNode);
        printf("\n");
    */
    /*
    //测试find_max_node
    BinarySearchTreeNode * node1 =  find_max_node(&ppNode);
    if(NULL!=node1){printf("\nx %d\n ",node1->key);}
    in_scan(&ppNode);
        printf("\n");
    */


    //测试删除delete_node_from_tree
    delete_node_from_tree(&ppNode,bst_data_array[1]);
    pre_scan(&ppNode);
    printf("\n");
    delete_tree(&ppNode);
   return 0;
}