首页 > 其他分享 >二叉查找树/堆 /Treap/Spaly树串联分析

二叉查找树/堆 /Treap/Spaly树串联分析

时间:2024-03-15 19:45:49浏览次数:20  
标签:node Node int value 二叉 Treap static key Spaly

二叉查找树 (BST)

二叉查找树:中序遍历是一个递增的序列。父节点的左子树的所有结点都比父节点小,父节点右子树的结点比父节点都大。

在一颗随机构造的BST上,查找一个元素的时间复杂度位O(logn) ,但是如果我们有序的插入结点,那么BST的高度将位N,时间复杂度位O(n) 。

import java.util.Scanner;
public class Main {

    static class Node {
        Node l;
        Node r;
        int value;
    }
    static Node insert(Node node, int value) {
        if (node == null) {
            node = new Node();
            node.value = value;
            return node;
        }

        if (node.value > value) {
            node.l = insert(node.l, value);

        } else {
            node.r = insert(node.r, value);

        }

        return node;

    }
    static void dfs(Node node) {

        if (node.l != null) {
            dfs(node.l);
        }

        System.out.print(node.value + " ");

        if (node.r != null) {
            dfs(node.r);
        }

    }
    
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        Node root = new Node();

        root.value = sc.nextInt();

        for (int i = 1; i < n; i++) {

            int value = sc.nextInt();

            insert(root, value);

        }
        dfs(root);
    }
}

堆的性质:堆顶元素为所有元素中最小(或者最大)。父结点 的左节点和右节点都比父节点大。
一维数组即可实现,父节点索引为 x ,左儿子索引为x 乘 2 ,右儿子索引 x 乘 2+1
核心操作:
down : 如果自己比两个儿子结点大,那么跟其中最小的进行换位。递归操作
up:同down差不多
删除堆顶元素 : 直接将最后一个元素提到堆顶,然后进行down操作
插入元素:插入最后一个位置,然后up操作

    import java.util.Scanner;

    public class Main {
        static int h[] = new int[200010];
        static int n;

        static void down(int index) {

            int a = h[index * 2];
            int b = h[index * 2 + 1];
            if (index * 2 > n) {
                a = 1000000000;
            }
            if (index * 2 + 1 > n) {
                b = 1000000000;
            }
            if (a < b && a < h[index]) {
                int tmp = h[index];
                h[index] = a;
                h[index * 2] = tmp;
                down(index * 2);
            }
            if (b <= a && b < h[index]) {
                int tmp = h[index];
                h[index] = b;
                h[index * 2 + 1] = tmp;
                down(index * 2 + 1);
            }
        }

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt();
            int m = sc.nextInt();
            for (int i = 1; i <= n; i++) {
                h[i] = sc.nextInt();
            }
            for (int i = n / 2; i != 0; i--) {
                down(i);
            }
            for (int i = 1; i <= n; i++) {
             //   System.out.println(h[i]);
            }
            while (m-- != 0) {
                System.out.print(h[1] + " ");
                h[1] = h[n--];
                down(1);
            }

        }
    }

Treap

Treap 就是 Tree + Heap

我们知道,一个BST可能面临退化为链表的问题。那么我们在属性Key(代表当前存储的值)之外,可以给结点加一个属性为Value 。在插入时,我们用随机函数给Value属性随机生成一个值。然后我们先把结点按照BST的性质(中序遍历输出属性K为递增)插入到对应的位置。但是到对应位置之后,当前的这颗树可能不符合堆的结构,我们递归的调用左旋,右旋去维护堆的性质。
那左旋和右旋是什么呢?就是保证不打乱树的中序遍历的情况下,交换两个结点。

```java
import java.util.Random;
import java.util.Scanner;

/**
 * Main
 */
public class Main {
    static int N = 100010;
    static int INF = 100000000;
    static int idx = 0;
    static Random random = new Random();

    static class Node {
        Node l, r;
        int key, value;
        int cnt, size;

        Node(int key) {
            this.key = key;
            this.value = random.nextInt();
            this.cnt = this.size = 1;
        }
    };

    static Node root = null;

    static void pushup(Node node) {
        node.size = node.cnt;
        if (node.l != null) {
            node.size += node.l.size;
        }
        if (node.r != null) {
            node.size += node.r.size;
        }
    }

    static void build() {
        Node node1 = new Node(INF);
        Node node2 = new Node(-INF);
        node1.l = node2;
        root = node1;
        if (node1.value < node2.value)
            root = zig(root);
        pushup(root);
    }

    static Node zig(Node node) {
        Node lt = node.l;
        node.l = lt.r;
        lt.r = node;
        node = lt;
        pushup(node.r);
        pushup(node);
        return lt;
    }

    static Node zag(Node node) {
        Node rt = node.r;
        node.r = rt.l;
        rt.l = node;
        node = rt;
        pushup(node.l);
        pushup(node);
        return rt;
    }

    static Node insert(Node node, int key) {
        if (node == null) {
            return new Node(key);
        } else if (node.key == key) {
            node.cnt++;
        } else if (node.key > key) {
            node.l = insert(node.l, key);
            if (node.l.value > node.value) {
                node = zig(node);
            }
        } else {
            node.r = insert(node.r, key);
            if (node.r.value > node.value) {
                node = zag(node);
            }
        }
        pushup(node);
        return node;
    }

    static Node remove(Node node, int key) {
        if (node == null) {
            return null;
        }
        if (node.key == key) {
            if (node.cnt > 1) {
                node.cnt--;
                pushup(node);
                return node;
            } else {
                if (node.l == null && node.r == null)
                    return null;
                if (node.l == null) {
                    node = zag(node);
                    node.l = remove(node.l, key);
                } else if (node.r == null) {
                    node = zig(node);
                    node.r = remove(node.r, key);
                } else if (node.l.value < node.r.value) {
                    node = zag(node);
                    node.l = remove(node.l, key);
                } else {
                    node = zig(node);
                    node.r = remove(node.r, key);
                }
            }
        } else {
            if (node.key > key) {
                node.l = remove(node.l, key);
            } else {
                node.r = remove(node.r, key);
            }
        }
        pushup(node);
        return node;
    }

    static int get_rank_by_key(Node node, int key) {

        if (node == null) {
            return 1;
        }
        int lsize = node.l == null ? 0 : node.l.size;
        if (key == node.key) {
            return lsize + 1;
        } else if (node.key > key) {
            return get_rank_by_key(node.l, key);
        } else {
            return lsize + node.cnt + get_rank_by_key(node.r, key);
        }
    }

    static int get_key_by_rank(Node node, int rank) {

        int lsize = node.l == null ? 0 : node.l.size;
        if (lsize < rank && lsize + node.cnt >= rank) {
            return node.key;
        } else if (lsize >= rank) {
            return get_key_by_rank(node.l, rank);
        } else {
            return get_key_by_rank(node.r, rank - node.cnt - lsize);
        }
    }

    static int get_prev(Node node, int key) {
        if (node == null)
            return -INF;
        if (node.key >= key) {
            return get_prev(node.l, key);
        }
        return Math.max(node.key, get_prev(node.r, key));
    }

    static int get_next(Node node, int key) {
        if (node == null) {
            return INF;
        }
        if (node.key <= key) {
            return get_next(node.r, key);
        }
        return Math.min(node.key, get_next(node.l, key));
    }

    public static void main(String[] args) {

        build();

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        while (n-- != 0) {
            int opt, x;
            opt = sc.nextInt();
            x = sc.nextInt();

            if (opt == 1) {
                root = insert(root, x);
            } else if (opt == 2) {
                root = remove(root, x);
            } else if (opt == 3) {
                System.out.println(get_rank_by_key(root, x) - 1);
            } else if (opt == 4) {
                System.out.println(get_key_by_rank(root, x + 1));
            } else if (opt == 5) {
                System.out.println(get_prev(root, x));
            } else {
                System.out.println(get_next(root, x));
            }

        }

    }
}

Splay

Splay 是为了解决BST退化的另一个方案。

基于程序局部性原理的假设,在一个结点被访问后,我们将把他放到树根的位置。

在把这个结点推向树根的过程中,我们对于不同的情况,选的不同的左旋和右旋方案,在完成操作的同时,减少树的层数,解决BST退化的问题。

标签:node,Node,int,value,二叉,Treap,static,key,Spaly
From: https://www.cnblogs.com/x1uc/p/18076113

相关文章

  • 洛谷题单指南-二叉树-P1030 [NOIP2001 普及组] 求先序排列
    原题链接:https://www.luogu.com.cn/problem/P1030题意解读:已知中序、后序,求先序。解题思路:与洛谷题单指南-二叉树-P1827[USACO3.4]美国血统AmericanHeritage非常类似,不在介绍过程,直接给出代码。100分代码:#include<bits/stdc++.h>usingnamespacestd;stringin,post......
  • 二叉树的垂序遍历
    说在前面......
  • L2-3 二叉搜索树的2层结点统计
    L2-3二叉搜索树的2层结点统计分数25作者陈越单位浙江大学二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉......
  • 数据结构之链式二叉树
    当我们初步了解二叉树后我们就可以进一步去深入学习二叉树了1.链式二叉树的遍历这里我们先去定义链式二叉树的结构分为两个指针一左一右他们分别指向左子树和右子树typedefintBTDataType;typedefstructBinaryTreeNode{ BTDataTypedata; structBinartTreeNode......
  • 108. 将有序数组转换为二叉搜索树c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/structTreeNode*build(int*nums,inthead,inttail){if(head>tail)returnNULL;intmid=head+(......
  • 669. 修剪二叉搜索树c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/structTreeNode*trimBST(structTreeNode*root,intlow,inthigh){if(!root)returnNULL;if(ro......
  • 代码随想录算法训练营第day17|110.平衡二叉树 、 257. 二叉树的所有路径 、404.左叶子
    目录a.110.平衡二叉树b.257.二叉树的所有路径 c.404.左叶子之和a.110.平衡二叉树力扣题目链接(opensnewwindow)给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。示例1......
  • 洛谷 P5018 对称二叉树
    题目背景NOIP2018普及组T4题目描述一棵有点权的有根树如果满足以下条件,则被轩轩称为对称二叉树:二叉树;将这棵树所有节点的左右子树交换,新树和原树对应位置的结构相同且点权相等。下图中节点内的数字为权值,节点外的 idid 表示节点编号。现在给出一棵二叉树,希望你找出......
  • P8681 [蓝桥杯 2019 省 AB] 完全二叉树的权值
    题目描述给定一棵包含N 个节点的完全二叉树,树上每个节点都有一个权值,按从上到下、从左到右的顺序依次是​,如下图所示: 现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的节点权值之和最大?如果有多个深度的权值和同为最大,请你输出其中最小的深度。注:根的深度是 1......
  • 二叉树
    节点类定义classTreeNode{privateStringvalue;privateTreeNodeleft;privateTreeNoderight;publicTreeNode(Stringvalue){this.value=value;this.left=null;this.right=null;}publicvoidsetLeft(Tr......