最新公告
  • 新注册用户请前往个人中心绑定邮箱以便接收相关凭证邮件!!!点击前往个人中心
  • 数据结构笔记总结(11.2)计算节点的高度和平衡因子

    计算节点的高度和平衡因子

    在上一小节中,为了保持二分搜索树的平衡,对每一个节点应该记录一个高度值,通过高度值可以得到平衡因子这样一个值,根据平衡因子可以进行一些后续的操作来保持平衡。

    改进原来的二分搜索树代码

    我们先改进原来的BST二分搜索树的代码,让它可以记录节点的高度值并计算平衡因子。

    import java.util.ArrayList;
    
    public class AVLTree, V> {
    
        private class Node{
            public K key;
            public V value;
            public Node left, right;
            public int height;
    
            public Node(K key, V value){
                this.key = key;
                this.value = value;
                left = null;
                right = null;
                height = 1;
            }
        }
    
        private Node root;
        private int size;
    
        public AVLTree(){
            root = null;
            size = 0;
        }
    
        public int getSize(){
            return size;
        }
    
        public boolean isEmpty(){
            return size == 0;
        }
    
        // 获得节点node的高度
        private int getHeight(Node node){
            if(node == null)
                return 0;
            return node.height;
        }
    
        // 获得节点node的平衡因子
        private int getBalanceFactor(Node node){
            if(node == null)
                return 0;
            return getHeight(node.left) - getHeight(node.right);
        }
    
        // 向二分搜索树中添加新的元素(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;
    
            // 更新height
            node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
    
            // 计算平衡因子
            int balanceFactor = getBalanceFactor(node);
            if(Math.abs(balanceFactor) > 1)
                System.out.println("unbalanced : " + balanceFactor);
    
            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;
            }
        }
    
        public static void main(String[] args){
    
            System.out.println("Pride and Prejudice");
    
            ArrayList words = new ArrayList<>();
            if(FileOperation.readFile("pride-and-prejudice.txt", words)) {
                System.out.println("Total words: " + words.size());
    
                AVLTree map = new AVLTree<>();
                for (String word : words) {
                    if (map.contains(word))
                        map.set(word, map.get(word) + 1);
                    else
                        map.add(word, 1);
                }
    
                System.out.println("Total different words: " + map.getSize());
                System.out.println("Frequency of PRIDE: " + map.get("pride"));
                System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));
            }
    
            System.out.println();
        }
    }
    

    源码下载

    [dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

    导航目录

    [dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 数据结构笔记总结(11.2)计算节点的高度和平衡因子

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    参与讨论

    • 127会员总数(位)
    • 3724资源总数(个)
    • 0本周发布(个)
    • 0 今日发布(个)
    • 300稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级