备案控制台
开发者社区 云计算 文章 正文

有序表之SB树

2022-04-04 150
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 有序表之SB树

SB树的平衡标准

任何以叔叔结点的为头的子树的结点个数不小于任何一个以自己侄子为头结点的子树的结点个数。

比如看下图，B结点是G，H结点的叔叔。所以，以B结点为头的整颗子树的结点个数不能小于以G或者H为头的整颗子树的结点个数。

同理，C结点是E，F结点的叔叔。所以，以C结点为头的整颗子树的结点个数不能小以E或者F为头的整颗子树的结点个数。

如果任何一个结点以叔叔的姿态满足这个标准，就是SB树
在这里插入图片描述

SB树的四种违规情况

LL型违规

查某一个父亲是LL型违规指的是：父亲的左儿子的左儿子的结点个数大于了父亲的右儿子的结点个数。

父亲并没有违规！是查父亲的孩子是否违规！！！
在这里插入图片描述

LR型违规

查某一个父亲是LR型违规指的是：父亲的左儿子的右儿子的结点个数大于了父亲的右儿子的结点个数。

在这里插入图片描述

RL型违规

查某一个父亲是RL型违规指的是：父亲的右儿子的左儿子的结点个数大于了父亲的左儿子的结点个数。

在这里插入图片描述

RR型违规

查某一个父亲是RR型违规指的是：父亲的右儿子的右儿子的结点个数大于了父亲的左儿子的结点个数。
在这里插入图片描述

SB树的平衡调整

之前在AVL树一文讲过，调整平衡的基础操作都是左旋和右旋，所以，SB树的平衡调整也是一样。但是SB树在完成基本操作后，如果某个结点的孩子发生变化了，就还要递归调用一个让自己变平衡的方法maintain()。

比如，下图中，A结点和父结点的孩子都发生了变化，所以还要递归调用方法maintain(A)和maintain(父)。
在这里插入图片描述

SB树的平衡调整结论

不管是属于四种违规类型的哪种，调整方式跟AVL树一样，都是左旋或者右旋；唯一的区别就是调整完后，哪个结点的孩子发生了变化，就要调到用递归！

在这里插入图片描述

SB树的优势

在左旋或者右旋完后，调用递归，就是SB树的优势。

具体来说，SB树在删除结点的时候不调整平衡性，哪怕是不平衡的，也先放着不管。只有在加入结点的时候才调整平衡性。所以，SB树实现有序表的优势就是省掉了删除时候的调整平衡性操作！

因为整棵树的平衡调整是递归行为，所以整棵树的平衡调整是有传递性的。

因此，删除结点的时候不调整平衡性，只在加入结点的时候才调整平衡性，整棵树依然能够变平衡。

package com.harrison.class26;

/**
 * @author Harrison
 * @create 2022-04-04-13:44
 * @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
 */
public class Code01_SizeBalancedTreeMap {
    public static class SBTNode<K extends Comparable<K>, V> {
        public K key;
        public V value;
        public SBTNode<K, V> l;
        public SBTNode<K, V> r;
        public int size; // 不同的key的数量

        public SBTNode(K key, V value) {
            this.key = key;
            this.value = value;
            size = 1;
        }
    }

    public static class SizeBalancedTreeMap<K extends Comparable<K>, V> {
        private SBTNode<K, V> root;

        private SBTNode<K, V> rightRotate(SBTNode<K, V> cur) {
            SBTNode<K, V> leftNode = cur.l;
            cur.l = leftNode.r;
            leftNode.r = cur;
            leftNode.size = cur.size;
            cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;
            return leftNode;
        }

        private SBTNode<K, V> leftRotate(SBTNode<K, V> cur) {
            SBTNode<K, V> rightNode = cur.r;
            cur.r = rightNode.l;
            rightNode.l = cur;
            rightNode.size = cur.size;
            cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;
            return rightNode;
        }

        private SBTNode<K, V> maintain(SBTNode<K, V> cur) {
            if (cur == null) {
                return null;
            }
            int leftSize = cur.l != null ? cur.l.size : 0;
            int leftLeftSize = cur.l != null && cur.l.l != null ? cur.l.l.size : 0;
            int leftRightSize = cur.l != null && cur.l.r != null ? cur.l.r.size : 0;
            int rightSize = cur.r != null ? cur.r.size : 0;
            int rightLeftSize = cur.r != null && cur.r.l != null ? cur.r.l.size : 0;
            int rightRightSize = cur.r != null && cur.r.r != null ? cur.r.r.size : 0;
            if (leftLeftSize > rightSize) {
                cur = rightRotate(cur);
                cur.r = maintain(cur.r);
                cur = maintain(cur);
            } else if (leftRightSize > rightSize) {
                cur.l = leftRotate(cur.l);
                cur = rightRotate(cur);
                cur.l = maintain(cur.l);
                cur.r = maintain(cur.r);
                cur = maintain(cur);
            } else if (rightRightSize > leftSize) {
                cur = leftRotate(cur);
                cur.l = maintain(cur.l);
                cur = maintain(cur);
            } else if (rightLeftSize > leftSize) {
                cur.r = rightRotate(cur.r);
                cur = leftRotate(cur);
                cur.l = maintain(cur.l);
                cur.r = maintain(cur.r);
                cur = maintain(cur);
            }
            return cur;
        }

        // 现在，以cur为头的树上，新增，加(key, value)这样的记录
        // 加完之后，会对cur做检查，该调整调整
        // 返回，调整完之后，整棵树的新头部
        private SBTNode<K, V> add(SBTNode<K, V> cur, K key, V value) {
            if (cur == null) {
                return new SBTNode<>(key, value);
            } else {
                cur.size++;
                if (key.compareTo(cur.key) < 0) {
                    cur.l = add(cur.l, key, value);
                } else {
                    cur.r = add(cur.r, key, value);
                }
                return maintain(cur);
            }
        }

        // 在cur这棵树上，删掉key所代表的节点
        // 返回cur这棵树的新头部
        public SBTNode<K, V> delete(SBTNode<K, V> cur, K key) {
            cur.size--;
            if (key.compareTo(cur.key) < 0) {
                cur.l = delete(cur.l, key);
            } else if (key.compareTo(cur.key) > 0) {
                cur.r = delete(cur.r, key);
            } else {// 当前要删掉cur
                if (cur.l == null && cur.r == null) {
                    // free cur memory -> C++
                    cur = null;
                } else if (cur.l == null && cur.r != null) {
                    // free cur memory -> C++
                    cur = cur.r;
                } else if (cur.l != null && cur.r == null) {
                    // free cur memory -> C++
                    cur = cur.l;
                }else{// 左右孩子都有
                    // 找到cur的后继结点替换cur
                    SBTNode<K,V> pre=null;
                    SBTNode<K,V> des=cur.r;// des来到当前结点的右孩子
                    des.size--;
                    while (des.l!=null){
                        pre=des;
                        des=des.l;
                        des.size--;
                    }
                    // while循环结束后，des来到了cur结点的右树的最左孩子
                    // 并且此时的des是叶子结点，没有孩子了
                    // pre来到最左孩子的父亲结点
                    if(pre!=null){
                        pre.l=des.r;// 最左孩子的父亲断掉最左孩子
                        des.r=cur.r;// 最左孩子接管cur的右子树
                    }
                    des.l=cur.l;// 还是接管原来的左子树
                    des.size=des.l.size+(des.r==null?0:des.r.size)+1;
                    cur=des;
                }
            }
            // return maintain(cur);
            return cur;
        }

        private SBTNode<K, V> findLastIndex(K key) {
            SBTNode<K, V> pre = root;
            SBTNode<K, V> cur = root;
            while (cur != null) {
                pre = cur;
                if (key.compareTo(cur.key) == 0) {
                    break;
                } else if (key.compareTo(cur.key) < 0) {
                    cur = cur.l;
                } else {
                    cur = cur.r;
                }
            }
            return pre;
        }

        private SBTNode<K, V> findLastNoSmallIndex(K key) {
            SBTNode<K, V> ans = null;
            SBTNode<K, V> cur = root;
            while (cur != null) {
                if (key.compareTo(cur.key) == 0) {
                    ans = cur;
                    break;
                } else if (key.compareTo(cur.key) < 0) {
                    ans = cur;
                    cur = cur.l;
                } else {
                    cur = cur.r;
                }
            }
            return ans;
        }

        private SBTNode<K, V> findLastNoBigIndex(K key) {
            SBTNode<K, V> ans = null;
            SBTNode<K, V> cur = root;
            while (cur != null) {
                if (key.compareTo(cur.key) == 0) {
                    ans = cur;
                    break;
                } else if (key.compareTo(cur.key) < 0) {
                    cur = cur.l;
                } else {
                    ans = cur;
                    cur = cur.r;
                }
            }
            return ans;
        }

        private SBTNode<K, V> getIndex(SBTNode<K, V> cur, int kth) {
            if (kth == (cur.l != null ? cur.l.size : 0) + 1) {
                return cur;
            } else if (kth <= (cur.l != null ? cur.l.size : 0)) {
                return getIndex(cur.l, kth);
            } else {
                return getIndex(cur.r, kth - (cur.l != null ? cur.l.size : 0) - 1);
            }
        }

        public int size() {
            return root == null ? 0 : root.size;
        }

        public boolean containsKey(K key) {
            if (key == null) {
                throw new RuntimeException("invalid parameter.");
            }
            SBTNode<K, V> lastNode = findLastIndex(key);
            return lastNode != null && key.compareTo(lastNode.key) == 0 ? true : false;
        }

        // （key，value） put -> 有序表 新增、改value
        public void put(K key, V value) {
            if (key == null) {
                throw new RuntimeException("invalid parameter.");
            }
            SBTNode<K, V> lastNode = findLastIndex(key);
            if (lastNode != null && key.compareTo(lastNode.key) == 0) {
                lastNode.value = value;
            } else {
                root = add(root, key, value);
            }
        }

        public void remove(K key) {
            if (key == null) {
                throw new RuntimeException("invalid parameter.");
            }
            if (containsKey(key)) {
                root = delete(root, key);
            }
        }

        public K getIndexKey(int index) {
            if (index < 0 || index >= this.size()) {
                throw new RuntimeException("invalid parameter.");
            }
            return getIndex(root, index + 1).key;
        }

        public V getIndexValue(int index) {
            if (index < 0 || index >= this.size()) {
                throw new RuntimeException("invalid parameter.");
            }
            return getIndex(root, index + 1).value;
        }

        public V get(K key) {
            if (key == null) {
                throw new RuntimeException("invalid parameter.");
            }
            SBTNode<K, V> lastNode = findLastIndex(key);
            if (lastNode != null && key.compareTo(lastNode.key) == 0) {
                return lastNode.value;
            } else {
                return null;
            }
        }

        public K firstKey() {
            if (root == null) {
                return null;
            }
            SBTNode<K, V> cur = root;
            while (cur.l != null) {
                cur = cur.l;
            }
            return cur.key;
        }

        public K lastKey() {
            if (root == null) {
                return null;
            }
            SBTNode<K, V> cur = root;
            while (cur.r != null) {
                cur = cur.r;
            }
            return cur.key;
        }

        public K floorKey(K key) {
            if (key == null) {
                throw new RuntimeException("invalid parameter.");
            }
            SBTNode<K, V> lastNoBigNode = findLastNoBigIndex(key);
            return lastNoBigNode == null ? null : lastNoBigNode.key;
        }

        public K ceilingKey(K key) {
            if (key == null) {
                throw new RuntimeException("invalid parameter.");
            }
            SBTNode<K, V> lastNoSmallNode = findLastNoSmallIndex(key);
            return lastNoSmallNode == null ? null : lastNoSmallNode.key;
        }

    }

    // for test
    public static void printAll(SBTNode<String, Integer> head) {
        System.out.println("Binary Tree:");
        printInOrder(head, 0, "H", 17);
        System.out.println();
    }

    // for test
    public static void printInOrder(SBTNode<String, Integer> head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.r, height + 1, "v", len);
        String val = to + "(" + head.key + "," + head.value + ")" + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.l, height + 1, "^", len);
    }

    // for test
    public static String getSpace(int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }

    public static void main(String[] args) {
        SizeBalancedTreeMap<String, Integer> sbt = new SizeBalancedTreeMap<String, Integer>();
        sbt.put("d", 4);
        sbt.put("c", 3);
        sbt.put("a", 1);
        sbt.put("b", 2);
        // sbt.put("e", 5);
        sbt.put("g", 7);
        sbt.put("f", 6);
        sbt.put("h", 8);
        sbt.put("i", 9);
        sbt.put("a", 111);
        System.out.println(sbt.get("a"));
        sbt.put("a", 1);
        System.out.println(sbt.get("a"));
        for (int i = 0; i < sbt.size(); i++) {
            System.out.println(sbt.getIndexKey(i) + " , " + sbt.getIndexValue(i));
        }
        printAll(sbt.root);
        System.out.println(sbt.firstKey());
        System.out.println(sbt.lastKey());
        System.out.println(sbt.floorKey("g"));
        System.out.println(sbt.ceilingKey("g"));
        System.out.println(sbt.floorKey("e"));
        System.out.println(sbt.ceilingKey("e"));
        System.out.println(sbt.floorKey(""));
        System.out.println(sbt.ceilingKey(""));
        System.out.println(sbt.floorKey("j"));
        System.out.println(sbt.ceilingKey("j"));
        sbt.remove("d");
        printAll(sbt.root);
        sbt.remove("f");
        printAll(sbt.root);
    }
}

下图是删除结点，左右孩子都有的情况。coding还是比较费力的
在这里插入图片描述

爱敲代码的Harrison
目录
相关文章
YoungMLet
|
8月前
【Leetcode -1609.奇偶树 -1122.数组的相对排序】
【Leetcode -1609.奇偶树 -1122.数组的相对排序】
YoungMLet
29 0
awo7k5oqgqada
|
8月前
【LeetCode】1609. 奇偶树、1122. 数组的相对排序
1609. 奇偶树 1609. 奇偶树 题目描述：
awo7k5oqgqada
32 0
xindoo
|
8月前
归并树&划分树详解
对4 5 2 8 7 6 1 3 分别建划分树和归并树
xindoo
35 0
Man9Oo
|
8月前
|
机器学习/深度学习 C++
AVL树的插入（C++实现）
AVL树的插入（C++实现）
Man9Oo
52 0
云与尘呀？
树的遍历
树的遍历
云与尘呀？
50 0
1169542316312847
|
算法
算法系列-多叉树的遍历
在内卷潮流的席卷下，身为算法小白的我不得不问自己，是否得踏上征程，征服这座巍巍高山。 从零开始，终点不知何方，取决于自己可以坚持多久。 希望你可以和我一样，克服恐惧，哪怕毫无基础，哪怕天生愚钝，依然选择直面困难。
1169542316312847
162 0
Lucky小黄人^_^
二叉查找树的建立，删除，非递归和递归查找给定元素，非递归和递归查找最大元素结点和最小元素结点
二叉查找树的建立，删除，非递归和递归查找给定元素，非递归和递归查找最大元素结点和最小元素结点
Lucky小黄人^_^
73 0
wait_
【CCCC】L2-006 树的遍历 (25分)，根据后序与中序遍历建立二叉树
【CCCC】L2-006 树的遍历 (25分)，根据后序与中序遍历建立二叉树
wait_
123 0
pushytao
|
算法
[leetcode] 1305. 两棵二叉搜索树中的所有元素 | 遍历
Java_code: cpp_code:
pushytao
91 0
[leetcode] 1305. 两棵二叉搜索树中的所有元素 | 遍历
Lux_Sun
ACM模板——树的创建（中 + 先、中 + 后、先 + 后）+ 树的遍历（先序、中序、中倒序、后序、层序）+ 求树高
ACM模板——树的创建（中 + 先、中 + 后、先 + 后）+ 树的遍历（先序、中序、中倒序、后序、层序）+ 求树高
Lux_Sun
106 0