简述

跳表是一种基于并联的链表，底层是一个普通的有序链表，更高层链表是基于随机方式构建的稀疏子链表，充当下层链表的快速通道，因此链表的长度由低到高层层递减。

跳表的查找、插入和删除操作的平均时间复杂度都为O(logn)，有效地解决有序链表查询效率低下的问题。

注意：跳表的最底层必须是一个有序链表。

简述

红黑树同AVL树一样也是一种自平衡二叉搜索树，不同于AVL树是高度平衡树，红黑树属于近似平衡树。

所谓近似平衡就是对平衡的要求相对宽松，不像AVL树那么严格。红黑数的平衡标准是：任一节点的左右子树的高度差小于两倍。

简述

AVL树是计算机科学中最早被发明的自平衡二叉搜索树，顾名思义，AVL首先是一颗平衡树，其次它能够实现自平衡。

简述

二叉查找树（Binary Search Tree），又叫有序二叉树，具有以下3个性质：

• 左子树如果不为空，那么它所有的节点的值都小于它的根节点
• 右子树如果不为空，那么它所有的节点的值都大于它的根节点
• 任意节点的左、右子树都是二叉查找树。