bst树的学习

柔情只为你懂 2022-01-27 13:35 182阅读 0赞

*  二叉排序树（BST）它是一种对排序和查找都很有用的特殊二叉树  
    具有下列性质  
    1.若它的左子树不为空，左子树上所有节点的值都小于根节点。  
    2.若它的右子树不为空，右子树上所有节点的值都小于根节点。  
    3.它的左，右子树也分别为二叉排序树。

讲解一下  
**二叉排序树的查找操作：**  
1.若二叉排序树为空，查找失败，返回空指针。  
2.若查找的值等于当前根节点的值，返回当前节点。  
查找的值大于当前的根节点，递归返回当前根节点的右子树  
小于就返回从根节点的左子树。  
算法：

void Search(BSTree T,Key key){
    		if(!T || key==T.data)return T;
    		if(key<T.data)return Search(T.left,key);
    		else if(T>T.data)return Search(T.right,key);
    }

插入操作：  
1.若BST为空，则待插入节点S作为根插入到空树种。  
2.若二叉排序树非空，则将key与根节点的关键字T.data进行比较。  
key<T.data,递归插入左子树  
否则，递归插入右子树

void InsertBst(BSTree &T,Key key){
    			if(!T){
    			S = new BSTNode;
    			s->data = e;
    			s->left = s->right = null;
    			T = S;
    			else if(e.key<T.data)
    			InsertBst(T->left,key);
    			else if(e.key>T.data){
    				InsertBst(T->right,key);
    			}
    }

**二叉排序树的删除**  
有这么几种情况  
1.缺右子树用左孩子填补  
2.缺左子树用右孩子填补  
3.在左子树上找中序最后一个节点填补，待删除的左右子树都存在  
或者也能在待删除节点的右子树中找中序遍历的第一个节点填补，待删除的左右子树都存在。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ_size_16_color_FFFFFF_t_70]

附带上代码

// 删除掉以node为根的二分搜索树中的最小节点
        // 返回删除节点后新的二分搜索树的根
        private Node removeMin(Node node) {
    
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
    
            node.left = removeMin(node.left);
            return node;
        }
    
        // 从二分搜索树中删除键为key的节点
        public V remove(K key) {
    
            Node node = getNode(root, key);
            if (node != null) {
                root = remove(root, key);
                return node.value;
            }
            return null;
        }
    
        private Node remove(Node node, K key) {
    
            if (node == null)
                return null;
    
            if (key.compareTo(node.key) < 0) {
                node.left = remove(node.left, key);
                return node;
            } else if (key.compareTo(node.key) > 0) {
                node.right = remove(node.right, key);
                return node;
            } else {   // key.compareTo(node.key) == 0
    
                // 待删除节点左子树为空的情况
                if (node.left == null) {
                    Node rightNode = node.right;
                    node.right = null;
                    size--;
                    return rightNode;
                }
    
                // 待删除节点右子树为空的情况
                if (node.right == null) {
                    Node leftNode = node.left;
                    node.left = null;
                    size--;
                    return leftNode;
                }
    
                // 待删除节点左右子树均不为空的情况
    
                // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
                // 用这个节点顶替待删除节点的位置
                Node successor = minimum(node.right);
                successor.right = removeMin(node.right);
                successor.left = node.left;
    
                node.left = node.right = null;
    
                return successor;
            }
        }

liuyubobobo老师那学习的BST

package com.hnist.lzn.AVLTree;
    
    public class BST<K extends Comparable<K>, V> {
    
        private class Node {
            public K key;
            public V value;
            public Node left, right;
    
            public Node(K key, V value) {
                this.key = key;
                this.value = value;
                left = null;
                right = null;
            }
        }
    
        private Node root;
        private int size;
    
        public BST() {
            root = null;
            size = 0;
        }
    
        public int getSize() {
            return size;
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
        // 向二分搜索树中添加新的元素(key, value)
        public void add(K key, V value) {
            root = add(root, key, value);
        }
    
        // 向以node为根的二分搜索树中插入元素(key, value)，递归算法
        // 返回插入新节点后二分搜索树的根
        private Node add(Node node, K key, V value) {
    
            if (node == null) {
                size++;
                return new Node(key, value);
            }
    
            if (key.compareTo(node.key) < 0)
                node.left = add(node.left, key, value);
            else if (key.compareTo(node.key) > 0)
                node.right = add(node.right, key, value);
            else // key.compareTo(node.key) == 0
                node.value = value;
    
            return node;
        }
    
        // 返回以node为根节点的二分搜索树中，key所在的节点
        private Node getNode(Node node, K key) {
    
            if (node == null)
                return null;
    
            if (key.equals(node.key))
                return node;
            else if (key.compareTo(node.key) < 0)
                return getNode(node.left, key);
            else // if(key.compareTo(node.key) > 0)
                return getNode(node.right, key);
        }
    
        public boolean contains(K key) {
            return getNode(root, key) != null;
        }
    
        public V get(K key) {
    
            Node node = getNode(root, key);
            return node == null ? null : node.value;
        }
    
        public void set(K key, V newValue) {
            Node node = getNode(root, key);
            if (node == null)
                throw new IllegalArgumentException(key + " doesn't exist!");
    
            node.value = newValue;
        }
    
        // 返回以node为根的二分搜索树的最小值所在的节点
        private Node minimum(Node node) {
            if (node.left == null)
                return node;
            return minimum(node.left);
        }
    
        // 删除掉以node为根的二分搜索树中的最小节点
        // 返回删除节点后新的二分搜索树的根
        private Node removeMin(Node node) {
    
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
    
            node.left = removeMin(node.left);
            return node;
        }
    
        // 从二分搜索树中删除键为key的节点
        public V remove(K key) {
    
            Node node = getNode(root, key);
            if (node != null) {
                root = remove(root, key);
                return node.value;
            }
            return null;
        }
    
        private Node remove(Node node, K key) {
    
            if (node == null)
                return null;
    
            if (key.compareTo(node.key) < 0) {
                node.left = remove(node.left, key);
                return node;
            } else if (key.compareTo(node.key) > 0) {
                node.right = remove(node.right, key);
                return node;
            } else {   // key.compareTo(node.key) == 0
    
                // 待删除节点左子树为空的情况
                if (node.left == null) {
                    Node rightNode = node.right;
                    node.right = null;
                    size--;
                    return rightNode;
                }
    
                // 待删除节点右子树为空的情况
                if (node.right == null) {
                    Node leftNode = node.left;
                    node.left = null;
                    size--;
                    return leftNode;
                }
    
                // 待删除节点左右子树均不为空的情况
    
                // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
                // 用这个节点顶替待删除节点的位置
                Node successor = minimum(node.right);
                successor.right = removeMin(node.right);
                successor.left = node.left;
    
                node.left = node.right = null;
    
                return successor;
            }
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ_size_16_color_FFFFFF_t_70]: /images/20220127/77f169126bcb4f7c9b902bee653321c7.png