红黑树、哈希表、堆

红黑树

红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。

红黑树的特性: (1)每个节点或者是黑色,或者是红色。 (2)根节点是黑色。 (3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!] (4)如果一个节点是红色的,则它的子节点必须是黑色的。 (5)==从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。==

注意: (01) 特性(3)中的叶子节点,是只为空(NIL或null)的节点。 (02) 特性(5),确保没有一条路径会比其他路径长出俩倍。==因而,红黑树是相对是接近平衡的二叉树。==

image-20210216221031160

应用

红黑树主要是用来存储有序的数据的

数据

红黑树的时间复杂度为: O(lgn)

一棵含有n个节点的红黑树的高度至多为2log(n+1).

操作

https://blog.csdn.net/wuzhenwei0419/article/details/84554049

红黑树的左旋

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
    * 左旋
    */
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                        TreeNode<K,V> p) {
    //这里的p即上图的A节点,r指向右孩子即C,rl指向右孩子的左孩子即D,pp为p的父节点
    TreeNode<K,V> r, pp, rl;
    if (p != null && (r = p.right) != null) {
        if ((rl = p.right = r.left) != null)
            rl.parent = p;
        //将p的父节点的孩子节点指向r
        // 如果A就是根节点,那么C换上来之后,要把它变成黑色,因为根节点都是黑色的
        if ((pp = r.parent = p.parent) == null)
            (root = r).red = false;
        else if (pp.left == p)
            pp.left = r;
        else
            pp.right = r;
        //将p置为r的左节点
        r.left = p;
        p.parent = r;
    }
    return root;
}

红黑树的右旋

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 右旋
*/
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                        TreeNode<K,V> p) {
        //这里的p即上图的A节点,l指向左孩子即C,lr指向左孩子的右孩子即E,pp为p的父节点
    TreeNode<K,V> l, pp, lr;
    if (p != null && (l = p.left) != null) {
        if ((lr = p.left = l.right) != null)
            lr.parent = p;
        if ((pp = l.parent = p.parent) == null)
            (root = l).red = false;
        else if (pp.right == p)
            pp.right = l;
        else
            pp.left = l;
        l.right = p;
        p.parent = l;
    }
    return root;
}

哈希表

通过哈希函数将key进行映射。

如何解决哈希冲突

开放地址

如果该地址已经存了,那就往后继续探测,直到找到空地址位置,存入数据。

在查询的时候,如果key对不上,则按相同的规则继续探测。

链表法

如果地址冲突了,把数据当作链表连接起来,存在同一个地址内。

查询的时候需要遍历链表

堆就是以二叉树的形式来维护一个数组。

分为大根堆和小根堆。大根堆父节点比子节点要大。