数据结构（二）--- 红黑树

一、简述红黑树是一种特殊的二叉树，并且是优秀的自平衡查找树，下图为红黑树的示例：红黑树具有以下几大特性：1、根节点为黑色。2、所有节点都是黑色或红色。3、所有叶子节点（Null）都是黑色。4、红色节点的子节点一定是黑色的。5、任意一个节点到其叶子节点的所有路径上的黑色节点数量相同（黑色完美平衡二叉树）。以上的五大特定也是维持红黑树结构的基本规则，但是明白了这些规则，不代表我们就明白了红黑树的设计原

数据结构（一）--- 跳跃表

1、简述跳跃表（skiplist）是一种优秀的数据查找结构，查找原理类似于2分查找，平均的查找时间复杂度为O(logN)；其底层基于链表实现，但区别在于含有多层，每个节点的每层都有指向表尾方向最近一个节点的指针；各种语言对跳跃表的实现可能不同，但主要原理是相同的，所以这里只是所以下原理，图中是含有四层结构的跳跃表，bw是指向前一个节点的指针，每个节点只有一个，删除时方便。每个节点都含有一个或多个指