数据结构-二叉搜索树与红黑树

4.二叉搜索树

又叫二叉查找树、有序二叉树、排序二叉树。树中任意一个结点，其左子树的每个节点值都要小于该节点，其右子树的每个节点值都要大于该节点

作用：能够进行快速查找、插入、删除操作

4.1 二叉搜索树的时间复杂度

注：二叉搜索树的形态各异，故时间复杂度也不尽相同

这里重点分析查找的时间复杂度，因为不管删除、插入操作，都要先进行查找目标。

4.1.1 查找时间复杂度

4.1.1.1 一般情况

分析：查找目标节点都要先从根节点开始找

eg：这里我们查找下图 值为5的节点，根据二叉搜索树的特点，首先我们要从结点开始，由于5比10小走左边到6的位置，由于5比6小继续走左边到4的位置，而5比4大故走右边，这里就找到5了，这里一共进行了3次对比找到了5。其他节点的查找方法也是这样。

下图，2的几次方代表每层的最大节点数量，而这个次方就代表对比的次数

故从上面得到，查找的时间复杂度为O(logn),由于上面说过，进行插入、删除操作都要进行查找操作，故它们两的时间复杂度也为O（logn）

4.1.1.2 特殊情况

这种情况就从二叉树退化为了链表，而链表的时间复杂度为O（n），故它的时间复杂度也为O（n） 。

5.红黑树

5.1 概念

也是一种自平衡的二叉搜索树（BST），以前叫作平衡二叉B树

5.2 红黑树特质（红黑规则）

5.2.1 节点要么是红色，要么是黑色

5.2.2 根节点必须是黑色

5.2.3 叶子节点都是黑色的空节点（标为null的都是空节点）

5.2.4 红黑树中红色节点的子节点都是黑色

5.2.5 从任意节点到叶子节点的所有路径都包含相同数目的黑色节点

注：再添加或删除节点时，如果不符和这些性质会发生旋转，以达到所有性质，也就是说这五个性质都是为了保证红黑树的平衡。

5.3 红黑树时间复杂度

5.3.1 查找

红黑树也h是一个二叉搜索树，故时间复杂度为O（logn）

5.3.2 添加

添加搜先要从查找操作开始，因为需要查找到目标添加位置，时间复杂度为O（logn），添加完成后，为了保证满足红黑树的特质即规则，故需要进行时间复杂度为O（1）的旋转调整操作。故总时间复杂度为O（logn）。

5.3.3 删除

删除搜先要从查找操作开始，因为需要查找到目标添加位置，时间复杂度为O（logn），删除完成后，为了保证满足红黑树的特质即规则，故需要进行时间复杂度为O（1）的旋转调整操作。故总时间复杂度为O（logn）。

即查找、添加、删除都是O（logn）