基础知识

综合类

c++


mysql


渗透测试

算法综合


rb tree

1、平衡二叉树

平衡二叉树就是为了解决二叉查找树退化成一颗链表而诞生了，平衡树具有如下特点
1、具有二叉查找树的全部特性。
2、每个节点的左子树和右子树的高度差至多等于1。
对于图二，因为节点9的左孩子高度为2，而右孩子高度为0。他们之间的差值超过1了。平衡树基于这种特点就可以保证不会出现大量节点偏向于一边的情况了。
于是，通过平衡树，我们解决了二叉查找树的缺点。对于有 n 个节点的平衡树，最坏的查找时间复杂度也为 O(logn)

2、为什么有了平衡树还需要红黑树？

虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logn)，不过却不是最佳的，因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树，红黑树具有如下特点：
1、具有二叉查找树的特点。
2、根节点是黑色的；
3、每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存数据。
4、任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的。
5、每个节点，从该节点到达其可达的叶子节点是所有路径，都包含相同数目的黑色节点。
正是由于红黑树的这种特点，使得它能够在最坏情况下，也能在 O(logn) 的时间复杂度查找到某个节点。至于为什么就能够保证时间复杂度为 O(logn)，我这里就不细讲了，后面的文章可能会讲。
不过，与平衡树不同的是，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整，这也是我们为什么大多数情况下使用红黑树的原因。
不过，如果你要说，单单在查找方面的效率的话，平衡树比红黑树快。
所以，我们也可以说，红黑树是一种不大严格的平衡树。也可以说是一个折中发方案。

3、总结

所以，最后的答案是，平衡树是为了解决二叉查找树退化为链表的情况，而红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况。
不过，红黑树还有挺多其他的知识点可以考，例如红黑树有哪些应用场景？向集合容器中 HashMap，TreeMap 等，内部结构就用到了红黑树了。还有构建一棵节点个数为 n 的红黑树，时间复杂度是多少？红黑树与哈希表在不同应该场景的选择？红黑树有哪些性质？红黑树各种操作的时间复杂度是多少？




排序

堆排序 

#include <iostream>
using namespace std;

void _heapify(int *a, int pos, int n)
{
    int largest_idx = pos;
    int l = pos * 2 + 1, r = pos * 2 + 2;
    if (l < n && a[l] > a[largest_idx])
        largest_idx = l;
    if (r < n && a[r] > a[largest_idx])
        largest_idx = r;
    if (largest_idx != pos)
    {
        swap(a[largest_idx], a[pos]);
        _heapify(a, largest_idx, n);
    }
}
void heapSort(int *a, int n)
{
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        _heapify(a, i, n);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        swap(a[0], a[i]);
        _heapify(a, 0, i);
    }
}
int a[1000000];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    heapSort(a, n);
    for (int i = 0; i < n; i++)
        cout << a[i] << ' ';
    return 0;
}