我的算法之路 -- BST二叉搜索树


我的算法之路 – BST二叉搜索树

Created by miccall (转载请注明出处)
  • 按理说这类文章首先应该讲一些鸡汤啊 鼓励学习什么的话       但是没有

  • 按理说这类文章应该有一些推荐路径或者学习方法       但是没有

  • 按理说这个文章应该和其他的类似 讲些算法之坑       但是没有

  • 那这篇文章出现的意义是什么 没什么 就是我的学习之路      你爱看就看看

  • 首先 必须是有序列 才能使用二分查找法

  • 对于有序列来说 要先比较数组中间的元素   ‘v’   与 我们想要查找元素 他俩的大小

  • 如果正好相等,那么很幸运 我们找到了这个元素 如果不是的话

  • 那么此时 ,数组就被 ‘v’ 分成了两半 一半全部小于’v’ ,另一半则大于 ‘v’。(所以要求是有序的)

  • 那么我就可以想 ,可以用递归的方法 ,在这两个分开的数组中 找我们想要找的元素了。

  • [ 不知道递归?? 那我也没办法 硬着头皮往下看呗 ]

erfen

  • 非常人性化的 这里我给出非递归的实现方式

  • 有兴趣的可以尝试递归的方式 或者网上一搜一大片。

        //首先我们给定有序列arr 长度n 搜索元素 target 返回他的位置 
        template <typename T>
        int BinarySearch(T arr[] , int n , T target)
        {
             //在 arr[l....r] 之中查找 target 
             int l = 0 , r = n-1 ; //区间 有边界是n-1 他是一个闭区间

             //当区间还有元素时 
             while( l <= r ) 
             {
                 //int mid = ( l + r ) / 2 ; 找到中间值 
                 //为了避免int不越值 我们重新换一种写法 
                 int mid = l + ( r - l ) / 2 ;

                 //很幸运的找到了 那么直接返回就好了
                 if( arr[mid] == target )
                     return mid ;

                 if( target < arr[mid] )
                     //在 arr[l.....mid-1] 中找target 
                     r = mid - 1 ;

                 else 
                     //在 arr[mid+1 ... r ] 中找target
                     l = mid + 1 ;    

             }
             //没找到返回-1 
             return -1 ;
        }

二分搜索树 Binary Search Tree

  • 是一个很强大的数据结构 他能高效的解决查找问题树

ecs

  • 构成二分搜索树的条件 :
  •   二叉树     &&
  •   每个节点的键值都大于左子树     &&
  •   每个节点的键值都小于右子树     &&
  •   以左右子树为根的子树依然要满足 二分搜索树
  • BST不一定是一个 完全二叉树
  • 所以我们不能用数组实现BST
  • 我们就只能用指针构建的Node节点来实现

BST

        template <typename Key,typename Value>
        class BinarySearchTree
        {
        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来构建一个新的node (copy)
                Node(Node *node){
                    this->key = node->key ;
                    this->value = node->value ;
                    this->left = node->left;
                    this->right = node->right;
                }

            };

            Node *root ; //根节点
            int count ; //计数

        }
  • 这样我们就构建了一个基本的BinarySearchTree类

  • 构造方法和析构方法我们简单的说一下 对于构造来说很简单 首先root 置为NULL count++

  • 对于析构来说 比较复杂 它涉及到DFS(深度优先搜索) 所以我们在文章的后半段来实现这个析构

  • 那我们先来实现几个简单的方法

        //构造 
        BinarySearchTree()
        {
            root = NULL ;
            count = 0 ;
        }
        //析构
        ~BinarySearchTree(){
            destory(root);
        }
        //树的大小
        int size()
        {
            return count ;
        }
        //树是否为空 
        int isEmpty()
        {
            return count == 0;
        }

二分搜索树 的方法

插入新的节点 Insert

  • 首先 要插入一个新的节点 我们就要拿这个节点与我们的树作比较 如果比root大 就要根root的右子树的根比较
    01
  • 相反 如果比root大 就要根root的左子树的根比较 ,直到发现root的某个子树的root为NULL 那么这个地方就是他应该所在的位置了 。
    02
  • 如果恰好找到了这个值相等的root,那我们就要用新的值 去覆盖原来的值 。
    03
        private : 
        //内部实现的递归的插入方法
        //在 node为根的树中 插入(k,v)

        Node * insert(Node *node ,Key key ,Value value)  
        {
            //向以node为根的BST中 插入节点(k,v)  返回值为新的BST的根节点

            if(node == NULL)
            {
                //如果子树为空 或者根为空 遇到为空的 ,就返回一个新节点
                count++ ;
                return new Node(key,value);
            }

            if(key == node->key) //与根相同的话  更新这个node  
                node->value = value ;
            else if(key < node->key)
            {
                //如果比node的值小,则去向左子树插入 我们递归的去把左子树的root传入,寻找合适的位置   
                node->left = insert(node->left,key,value);
            } else {
                //如果比node的值大,则插入到右子树
                node->right = insert(node->right ,key,value);
            }
            return node;
        }

        public :

        //外界调用的插入方法
        void insert (Key key ,Value value)
        {
            root = insert(root,key,value);
        }
  • 这样,我们就做完了向一个二分搜索树中插入元素的操作 ,接下来,我们要做的就是在这个树里面去寻找节点了。

寻找节点是否存在 contain

  • 思路其实跟插入的思路是一样的,我们判断我们要找的key是不是与根节点相同 否则的话 再根据key的大于与node.key的大小递归的去他的左右子树去寻找。
        private : 

        //在 node为根的树中 是否包含key
        bool contain(Node *node ,Key key)
        {
            if(node == NULL)
            {
                //如果直到叶子节点还没找到 返回false 
                return  false ; 
            }

            /*
                同样的思路 我们判断我们要找的key是不是与根节
                点相同 否则的话 再根据key的大于与node.key
                的大小递归的去他的左右子树去寻找 
            */
            if(key == node->key ) return  true ;  

            else if( key < node->key) return contain(node->left,key);

            else return  contain(node->right,key);

        }

        public :

        bool contain(Key key )
        {
            return contain(root,key);
        }
  • search函数的设计方法有很多种 也是根据自己的实际情况去设计 ,难点不是查找的算法 而是这个函数的返回值

  • 有些情况 ,直接返回返回一个node节点 这就要去外界人员去了解node的内部构造 这显然是很麻烦的

  • 还有情况 返回的是node.value 这个情况也有很多问题 首先你必须保证value的值不为空 否侧c++语言是不能为一个int返回NULL的

  • 这样,我们在研究算法 ,我们当然要考虑值的安全性 所以这里 我们以Value* 作为返回值 这样 当他的值不存在是 指针是可以返回一个NULL表示的 。

  • 了解了这个 算法其实就很好解决了 ,我们按照前面所讲的思路 递归的对他进行查找

        public :
        //在node为根的树中 搜索包含key的值

        Value* search(Node *node ,Key key)
        {
            //找不到的情况 就返回NULL
            if(node == NULL)
            {
                return  NULL ;
            }
            /*
                同样,我们分三种情况对他进行二分搜索 
                这里 我们的返回值是 当前找到的这个根节点 他的value值所在的地址 
                清楚了这个 我们就可以按照先前的思路 对他进行递归查找了 
            */
            if(key == node->key ) return  &(node->value) ;

            else if( key < node->key) return search(node->left,key);

            else return  search(node->right,key);

        }

        private :  

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

DFS(深度优先搜索)

  • DFS 深度优先搜索 顾名思义 他是一个树一个树 从根节点 一至到叶子节点的遍历

  • 我么们来讲三种遍历方法的共同点和不同点 大家可以先草率的看一下代码 就会发现 出奇的相似 只是改了一下名称和顺序

  • 对 这就是三个顺序的遍历 其实他们走过的路径是一模一样的

  • 他的思想就是 只有节点不为空 他就一直向着他的孩子节点递归 直到为空返回 返回回来 他又会向着另一边深入去递归 直到找到叶子节点为空

  • 每一个节点都会被路过三次 转个圈也算三次 (看似三次) 那么这三种遍历方法区别就在于 第几次遍历他的时候 打印他的值 。

前序遍历 preOrder
        private : 

        //在node为根的树中 对他进行前序遍历
        void preOrder(Node *node)
        {
            if(node != NULL)
            {
                cout<<node->key<<endl;
                preOrder(node->left);
                preOrder(node->right);
            }
        }

        public :

        void preOrder()
        {
            preOrder(root);
        }
中序遍历 inOrder
        private : 

        //在node为根的树中 对他进行中序遍历
        void inOrder(Node *node)
        {
            if(node != NULL)
            {
                inOrder(node->left);
                cout<<node->key<<endl;
                inOrder(node->right);
            }
        }

        public :

        void inOrder()
        {
            inOrder(root);
        }
后序遍历 postOrder
        private : 

        //在node为根的树中 对他进行后序遍历
        void postOrder(Node *node)
        {
            if(node != NULL)
            {
                postOrder(node->left);
                postOrder(node->right);
                cout<<node->key<<endl;
            }
        }

        public :

        void postOrder()
        {
            postOrder(root);
        }
  • 如何去理解三种遍历方法 我也给出了 一种简单的方法去记 。

  • 每一个节点都被箭头指向三次 第几次被指 就是什么遍历

  • 红箭头指向
    前

  • 绿箭头指向
    中
  • 蓝箭头指向
    后

  • 还不理解?那么看动画吧

前

  • 前序遍历:按从上到下,先左后右的原则。

中

  • 中序遍历:按从左向上,先下后上的原则。

后

  • 后序遍历:按从左到右,先下后上的原则。

BSF (广度优先搜索) levelOrder 层次遍历

  • 层次遍历对比与DFS的重要性和复杂性来说要低很多 但也是非常重要的思想

  • 他是层次遍历 也就是所 他是一级一级遍历的 所以我们得想办法记录不同的根节点

  • 很容易我们想到 可以用队列的方式来暂时存取我们记录的层的节点

  • 当一层遍历结束 我们从队列的最前面取出一个节点 对他的子节点进行入队 这样 第一层结束后 紧接着的就是第二层的遍历

  • 以此类推 。

        private :

        //在node为根的树中 对他进行层序遍历
        void levelOrder(Node *root)
        {
            queue<Node*> q ; 
            q.push(root);
            //当队列不为空我们对他进行遍历 
            while (!q.empty())
            {
                Node *node = q.front();  //取出一个节点 
                q.pop();    //让这个点处队 

                cout<<node->key<<endl; // 打印这个点 

                if(node->left) q.push(node->left);  //如果她有左子树 那么把他入队 
                if(node->right) q.push(node->right);  //同时 如果她有右子树 也把他入队 
            }
        }


        public : 

        void levelOrder()
        {
            levelOrder(root);
        }

寻找最大值与最小值

  • 如果你前面都非常理解了 就会很容易的知道 最大值 就在最右的子节点 相同的 最小值 就在最左的字节点

        private : 

        //寻找最小值 以node为根的树找最小值 返回最小值节点 
        Node * minimum(Node *node){

            if(node->left==NULL)
                return node ;

            return minimum(node->left); // 一直向左子树寻找 
        }

        //寻找最大值 以node为根的树找最大值 返回最大值节点
         Node * maximum(Node *node){

            if(node->right==NULL)
                return node ;

            return maximum(node->right); //向右子树寻找 
        }

        public :

        Key minimum(){
            assert(count != 0 );
            Node* minNode = minimum(root); 
            return minNode->key; 
        }

        Key maximum(){
            assert(count != 0 );
            Node *maxNode = minimum(root);
            return maxNode->key;
        }

移除最大值与最小值

  • 移除最小值有两种情况 一种是他没有右子树 那么问题就简单了 我们可以直接移除这个值

  • 但是另一种情况 他有右子树 我们怎样处理呢 其实也简单 。他的右子树虽然都比他本身大 但是肯定比他的父亲节点小 ,所以我们只要简单的 把右子树的节点移过来 代替删除的最小节点 ,让他成为最小值父亲的左子树 ,就可以了。

  • 类似的情况 我们删除他的最大值也是这样 如果他有左孩子的话 因为他的左孩子依然是一个二分搜索树 。也可以直接把他移过来就可以了 。

        private//移除最小值 删除以node为根的BST中的最小值 返回删除之后新的根 
        Node * removeMin(Node* node ){
            if(node ->left == NULL) //如果左子树为空 那么我们找到了这个最小值 
            {
                Node * rightNode = node->right ;   //看看右子树是否存在 为NULL也可以 
                delete node ;  //删除 node 
                count-- ;      
                return rightNode ; //  
            }
            node->left = removeMin(node->left);  //继续寻找 
            return  node ;  //返回这个根 
        }

        //移除最大值 同理 
        Node * removeMax(Node* node ){
            if(node ->right == NULL)
            {
                Node * leftNode = node->left ;
                delete node ;
                count-- ;
                return leftNode ;
            }
            node->right = removeMin(node->right);
            return  node ;
        }

        publicvoid removeMin()
        {
            if(root) // 如果根不会空 
                root = removeMin( root );
        }

        void removeMax()
        {
            if(root)
                root = removeMax( root );
        }

移除任意一个值

  • 1.为什么要讲删除最大值和最小值呢 因为最坏的情况下 最小值只有右孩子 最大值只有左孩子 这为我们删除任意值奠定了基础。因为这种方法可以删除任意一个只有一个孩子的节点。

  • 2.最难的情况可想而知了 删除一个任意一个节点 他可以有左右两个子树 。

  • 3.假设我们删除一个节点 我们设他为 d 据我们的经验 删除这个节点 ,必定要找一个值来代替他 ,那么是从他的左右孩子中找吗 ,那不一定 我们想 应该是找一个最接近他的值才可以 但是我们也知道 以d为根的子树 右边得找一个最小值 左边得找一个最大值 才能最接近d 。

  • 4.那我们就假设是 s 是d 的取代值 那么 s = min(d.right)

  • 5.找到s之后呢 我们先拿出来s节点 ,然后就要用我们之前的方法 删除d.right的最小值 也就是s节点, 然后把拿出来的s节点的右子树指向这个d.right。 然后 s.left = d.left 这个左子树不能丢 也得找到 。

  • 6.这样就就绪了 那么现在就可以放心的删除d这个节点了。 这样 s 就是新的子树的根

  • 其实,我们也可以找 s = max(d.left) 同样也是可以的 这里我们就不写了

  • O(logn)

        private :

        //删除以node为根 树中键值为key的节点
        //返回一个删除节点后的新的 根

        Node* remove(Node *node, Key key)
        {
            if(node == NULL)  //找不到这个节点 
                return  NULL; 
            if(key < node->key) 
            {
                //二分搜索
                node->left = remove(node->left,key); 
                return node;
            }
            else if(key>node->key)
            {
                //二分搜索
                node->right = remove(node->right,key);
                return node;
            }
            else{

                // 找到了这个节点node 

                if(node->left == NULL)  //只有右孩子
                {
                    Node * rightnode = node->right ;
                    delete node ;
                    count -- ;
                    return rightnode ;
                }

                if(node->right == NULL) //只有左 孩子
                {
                    Node * leftnode = node->left ;
                    delete node ;
                    count -- ;
                    return leftnode ;
                }

                // 有两个孩子 

                //Node * delnode = node ;  先保存这个节点(其实没必要)

                Node * successor = new Node(minimum(node->right)); 
                // node的最小值所在的节点 就是我们要拿来替换的节点 这里我们为了避免指针指向失败的问题 重新开一个空间节点 

                count++ ;

                successor->right = removeMin(node->right);  
                //removeMin的时候 会把successor delete掉 导致successor失效 所以我们必须开一个新的节点来存储这个值 

                successor->left = node->left ;  

                //删除这个节点  
                delete node;
                count -- ;
                return successor ;  //新的节点 
            }

        }

        public :

        //删除键值为key的节点 
        void remove(Key key)
        {
            root = remove(root,key);
        }

析构函数

  • 有了前面一大片的铺垫 相信这个析构函数就很好解决了 我们通过对他进行后序遍历 并把他一个一个销毁

        private :
        //在node为根的树中 对他进行后序遍历 并把他销毁
        void destory(Node *node)
        {
            if(node != NULL){
                destory(node->left);
                destory(node->right);

                delete node;
                count-- ;
            }
        }
        public :
        ~BinarySearchTree(){
            destory(root);
        }

其他的一些知识

  • 排序
  • 最大最小值
  • 前驱后继
  • floor和ceil
    floor表示 : 如果树中没有key 那么 就找最接近这个值,且小于这个值的key所对应的value
    ceil正好相反 如果树中没有key 那么 就找最接近这个值,且大于这个值的key所对应的value
  • rank和select
    rank : 某一个key在一个树中排名第几
    select : 在一个树中 排名第n的元数是谁
  • 支持重复元素的二分搜索

BST的局限性

  • 同样的数据 ,可能对应不同的BST 一个顺序的存入方式 可以使得一个树退化成一个链表 。可能导致比顺序查找都慢 (递归的时间消耗和两个指针的搜索)

  • 解决方法 : 平衡二叉树 __红黑树,2-3树,AVL树,Splay树等 使二叉树不能退化成链表

  • 平衡二叉树和堆的结合__ Treap

其他递归问题

  • 归并排序
  • 快速排序
  • 搜索问题
  • 决策树
  • 8数码
  • 8皇后
  • KD树 区间树 哈夫曼树