二叉树+二叉搜索树+红黑树

java
25

二叉树

二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。

不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。

二叉树每个节点的左子树和右子树也分别满足二叉树的定义。

二叉搜索树

在二叉树中，比较常见的二叉树有：

  • 二叉搜索树

  • 红黑树

概述

二叉搜索树(Binary Search Tree,BST)又名二叉查找树，有序二叉树或者排序二叉树，是二叉树中比较常用的一种类型

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值

时间复杂度分析

由于二叉查找树的形态各异，时间复杂度也不尽相同，

下图为 插入，查找，删除 的时间复杂度

插入，查找，删除的时间复杂度O(logn)

极端情况下二叉搜索的时间复杂度

图中这种情况属于最坏的情况，二叉查找树已经退化成了链表，左右子树极度不平衡，此时查找的时间复杂度肯定是O(n)。

红黑树

红黑树（Red Black Tree）：也是一种自平衡的二叉搜索树(BST)，之前叫做平衡二叉B树（Symmetric Binary B-Tree）

红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。

红黑树的特质

性质1：节点要么是红色,要么是黑色

性质2：根节点是黑色

性质3：红色节点不能相邻

性质4：红黑树中红色节点的子节点都是黑色（null视为黑色）

性质5：从任一节点到叶子节点的所有路径都包含相同数目的黑色节点（黑色完美平衡）

注意：在添加或删除节点的时候，如果不符合这些性质会发生旋转，以达到所有的性质，保证红黑树的平衡

不符合特质的例子：

  • 红色节点不能相邻

  • 黑色不平衡

旋转操作（主要看3，4，5符不符合）

旋转目的就是为了进行红黑树结构调整，达到平衡的目的。手段有 重新着色 + 旋转

左旋与右旋

T1与T2是轴对称关系

①、通过左旋和右旋来调整树的结构，避免某一侧过深。


②、染⾊，修复红黑规则，从而保证树的高度不会失衡。

时间复杂度分析

  • 查找：

    • 红黑树也是一棵BST（二叉搜索树）树，查找操作的时间复杂度为：O(log n)

  • 添加：

    • 添加先要从根节点开始找到元素添加的位置，时间复杂度O(log n)

    • 添加完成后涉及到复杂度为O(1)的旋转调整操作

    • 故整体复杂度为：O(log n)

  • 删除：

    • 首先从根节点开始找到被删除元素的位置，时间复杂度O(log n)

    • 删除完成后涉及到复杂度为O(1)的旋转调整操作

    • 故整体复杂度为：O(log n)

散列表

散列表（Hash Table）概述

散列表(Hash Table)又名哈希表/Hash表，是根据键（Key）直接访问在内存存储位置值（Value）的数据结构，

它是由数组演化而来的，利用了数组支持按照下标进行随机访问数据的特性。

散列函数和散列冲突

将键(key)映射为数组下标的函数叫做散列函数。可以表示为：hashValue = hash(key)

散列函数的基本要求：

  • 散列函数计算得到的散列值必须是大于等于0的正整数，因为hashValue需要作为数组的下标。

  • 如果key1==key2，那么经过hash后得到的哈希值也必相同即：hash(key1) == hash(key2）

  • 如果key1 != key2，那么经过hash后得到的哈希值也必不相同即：hash(key1) != hash(key2)

实际的情况下想找一个散列函数能够做到对于不同的key计算得到的散列值都不同几乎是不可能的，即便像著名的MD5,SHA等哈希算法也无法避免这一情况，这就是散列冲突(或者哈希冲突，哈希碰撞，就是指多个key映射到同一个数组下标位置)

散列冲突-链表法（拉链）

在散列表中，数组的每个下标位置我们可以称之为桶（bucket）或者槽（slot），每个桶(槽)会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

如果有多个key最终的hash值是一样的，就会存入数组的同一个下标中，下标中挂一个链表存入多个数据

时间复杂度-散列表

1，插入操作，通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，插入的时间复杂度是 O(1)

2，当查找、删除一个元素时，通过散列函数计算出对应的槽，然后遍历链表查找或者删除

  • 平均情况下基于链表法解决冲突时查询的时间复杂度是O(1)

  • 散列表可能会退化为链表,查询的时间复杂度就从 O(1) 退化为 O(n)

像这样多个key映射到同一个数组下标位置，就会退化成链表，时间复杂度就是O(n)

优化办法

将链表法中的链表改造为其他高效的动态数据结构，比如红黑树，查询的时间复杂度是 O(logn)

将链表法中的链表改造红黑树还有一个非常重要的原因，可以防止DDos攻击

DDos 攻击:

分布式拒绝服务攻击(英文意思是Distributed Denial of Service，简称DDoS）

指处于不同位置的多个攻击者同时向一个或数个目标发动攻击，或者一个攻击者控制了位于不同位置的多台机器并利用这些机器对受害者同时实施攻击。由于攻击的发出点是分布在不同地方的，这类攻击称为分布式拒绝服务攻击，其中的攻击者可以有多个