bst二叉树

缺乏、安全感 2021-12-16 14:27 306阅读 0赞

首先bst,又叫二叉查找树，且每个节点的键都大于其左子树中的任意节点，而小于右子树中的任意节点的键。

从算法中学习到的知识：

最根本性的意义是对插入和查找操作在二叉查找树中如果达到平衡那么这2个操作的时间复杂度都会降到O（logn）.这大大降低时间复杂度。

但是，也相应的需要注意它的不足，如果不是特别平衡，考虑极端情况，就会变相成为单链表。那么时间复杂度就会变成O（N）。所以，保证数据的操作让二叉查找树尽可能平衡是特别重要的。

首先定义基本的节点：

*  就是建立一个节点内部类
 *  树有一个root根节点
 *  其次，每个节点都拥有一个包括当前节点的子节点数目值N。

public class BSTTree<Key extends  Comparable<Key>,Value> {
    
        private Node root;
    
        private class Node {
    
            private Key key;
            private Value val;
            private Node left, right;
            private int N;
    
            public Node(Key key, Value value, int N) {
    
                this.key = key;
                this.val = value;
                this.N = N;
    
            }
        }

接下来讲讲二叉查找树的插入和查找方法：

查找方法：

其实就是一个二分查找，因为二叉查找树满足，当前节点左子树任意节点，大于右子树的任意节点，所以能利用二分查找，这也是二叉查找树的时间复杂度能降低logN的级别。

附上代码：

public Value get(Key key){
                return get(root,key);
            }
            private Value get(Node x,Key key){
    
                if(x==null)return null;        //判断当前节点存在吗？
                int cmp = key.compareTo(x.key);//从node节点比较key
    
                if(cmp<0)return get(x.left,key);//小于则从左侧开始递归
                else if(cmp>0)return get(x.right,key);//右侧
                else return x.val;    //当上述都不满足就代表node找到，返回nde即可
            }

插入方法：

这里分为即需要插入的节点，存在于树中，那么我们便更新当前的节点值。

如果不存在这个节点，就分2种情况，即当前插入的节点为root根节点，或者从以root为根节点的数中插入当前需要插入的节点。

由于，这个插入，也是根据二分的特性，即不断二分，再加上单独的操作，时间复杂度同样是O(logN)级别的。

附上代码：

public void put(Key key,Value value){  //每次调用这个方法插入
    
                root = put(root,key,value);    //即从root开始插入，如果当前root为null,即构造
                                               //以root的根节点。插入的节点不是root,则是从root存在
                                               //的情况下往树中插入.
            }
            private Node put(Node x,Key key,Value value){   
    
                if(x==null)return new Node(key,value,1);
                int cmp = key.compareTo(x.key);        //如果root存在，那么便在树中二分，不断插入
                if(cmp<0)x.left = put(x.left,key,value); //用x.left去链接递归到底构造的节点。
                else if(cmp>0)x.right = put(x.right,key,value);//同上.
                else
                    x.val = value;
                x.N = size(x.left)+size(x.right)+1;   //当递归进行时,也会子节点不断加1(重要)
                                                      //递归树回溯的过程中，每个节点都会更新当前的N  
                return x;  //  同样当前节点都会被返回。
            }

以上二叉查找树的主要方法就被完成了。

接下来讲讲书上的min,max以及floor方法

min方法就是不断从传入的节点不断左递归。递归到下一节点为null，返回即可。

那么max同上

//min
            public Key min(){
    
                return min(root).key;
            }
            private Node min(Node x){
                if(x.left==null)return x;
    
                return min(x.left);
            }
    
            //max
            public Key max(){
    
                return max(root).key;
            }
            private Node max(Node x){
                if(x.right==null)return x;
                return max(x.right);
            }

floor方法就是：

如果给定的键小于当前的root节点，那么小于等于key的最大键在一定在root节点的左子树种。

同理，如果给定的键大于当前的root节点，那么只有当前根节点右子树中存在小于等于key的节点，小于等于Key最大键才会出现在右子树中，否则根节点就是小于等key的最大键。

代码：

public Key floor(Key key){  
    
                Node x = floor(root,key);  //从root开始得到节点
                if(x==null)return null;    //判断x==null,是，return null,否则return x
                return x.key;
            }
            private Node floor(Node x,Key key){  //具体查找方法
    
                if(x==null)return null;          
                int cmp = key.compareTo(x.key);
                if(cmp==0)return x;
                if(cmp<0)return floor(x.left,key);  //小于就左递归,会返回给某个节点的
                Node t = floor(x.right,key);        //大于就右递归
                if(t!=null)return t;            //找到就返回。
                else                            //
                    return x;                    //没找到，返回的它的父节点
            }

其次最重要的就是删除操作了。

删除操作就分为删除最大键和删除最小键以及单独删除的操作

//deleteMin       
            public void deleteMin(){       //从root节点开始删除
    
                root = deleteMin(root);
    
            }
    
            private Node deleteMin(Node x){    //从具体得节点删除它的最小
                                               //即不断左递归
                if(x.left==null)return x.right;//如果当左子节点为空，返回右子节点，删除父节点。
                x.left = deleteMin(x.left);
                x.N = size(x.left)+size(x.right)+1; //删除后都要更新当前的节点值。
                return x;
    
    
            }
            //deleteMax
            public void deleteMax(){
                root = deleteMax(root);
            }
            private Node deleteMax(Node x){
    
                if(x.right==null)return x.left;
                x.right = deleteMax(x.right);    
                x.N = size(x.left)+size(x.right)+1;
                return x;
            }

最重要的也是删除操作，借助了上面的删除最小，最大的方法：

怎么去删除一个拥有2个子节点的节点呢？删除之后怎么处理2个子树？同时被删除的节点

*  **也会空出它的父节点的连接，T.Hibbard提出解决办法.**

在删除x节点后用它的后继节点填补它的位置。因为x有一个右子节点，因此它的后继节点，就是其右子树中的最小节点，这样的替换仍能保持树的有序性。因为x.key和它的后继节点的键之间不存在其他的键。

4个步骤：

将指向即将被删除的节点的连接保存为t；

将x指向它的后继节点min（t.right）;

将x的右链接指向deleteMin(t.right)，也就是在删除后所有节点仍旧大于x.key的子二叉查找树。

将x的左链接设为t.left

public void delete(Key key){
        
                root = delete(key,root);
    
            }
    
            /**
             * 删除操作
             * @param key
             * @param x
             * @return
             */
            private Node delete(Key key,Node x){
    
                if(x==null)return null;
    
                int cmp = key.compareTo(x.key);
                if(cmp<0)x.left = delete(key,x.left);
                else if(cmp>0)x.right = delete(key,x.right);
                else{
                    if(x.right==null)return x.left;
                    if(x.left==null)return x.right;
                    Node t = x;    //拿到被删除的节点
                    x = min(t.right);   //拿x重新指向的待删除的节点的右子树的最小节点
                    x.right = deleteMin(t.right);//先删除待删除节点的右子树最小节点，其次返回原先        
                                                 //待删除节点的右子树根节点。
                    x.left = t.left;            //x链接原先待删除节点的左子树节点
                }
                x.N = size(x.left)+size(x.right)+1;
    
                return x;                    //最后把后继节点返回，链接给原先待删除节点的原先位置
            }