数据结构Data Structure Visualizationshttps://www.cs.usfca.edu/~galles/visualization/Algorithms.html二叉树Binary Tree定义二叉树binary tree是指树中节点的度不大于2的有序树它是一种最简单且最重要的树。二叉树的递归定义为二叉树是一棵空树或者是一棵由一个根节点和两棵互不相交的分别称作根的左子树和右子树组成的非空树左子树和右子树又同样都是二叉树特点二叉树是每个节点最多有两个子节点的树二叉树的叶子节点有0个字节点二叉树的根节点或者内部节点有一个或者两个字节点。相关术语①结点包含一个数据元素及若干指向子树分支的信息 。②结点的度一个结点拥有子树的数目称为结点的度 。③叶子结点也称为终端结点没有子树的结点或者度为零的结点 。④分支结点也称为非终端结点度不为零的结点称为非终端结点 。⑤树的度树中所有结点的度的最大值 。⑥结点的层次从根结点开始假设根结点为第1层根结点的子节点为第2层依此类推如果某一个结点位于第L层则其子节点位于第L1层 。⑦树的深度也称为树的高度树中所有结点的层次最大值称为树的深度 。⑧有序树如果树中各棵子树的次序是有先后次序则称该树为有序树 。⑨无序树如果树中各棵子树的次序没有先后次序则称该树为无序树 。⑩森林由mm≥0棵互不相交的树构成一片森林。如果把一棵非空的树的根结点删除则该树就变成了一片森林森林中的树由原来根结点的各棵子树构成 。二叉搜索树Binary Search Tree定义二叉排序树Binary Sort Tree又称二叉查找树Binary Search Tree亦称二叉搜索树。是数据结构中的一类。在一般情况下查询效率比链表结构要高。特点一棵空树或者是具有下列性质的二叉树1若左子树不空则左子树上所有结点的值均小于它的根结点的值2若右子树不空则右子树上所有结点的值均大于它的根结点的值3左、右子树也分别为二叉排序树4没有键值相等的结点。BST树的搜索从根结点开始如果查询的关键字与结点的关键字相等那么就命中否则如果查询关键字比结点关键字小就进入左儿子如果比结点关键字大就进入右儿子如果左儿子或右儿子的指针为空则报告找不到相应的关键字.如果BST树的所有非叶子结点的左右子树的结点数目均保持差不多平衡那么B树的搜索性能逼近二分查找但它比连续内存空间的二分查找的优点是改变BST树结构插入与删除结点不需要移动大段的内存数据甚至通常是常数开销但BST树在经过多次插入与删除后有可能导致不同的结构右边也是一个BST树但它的搜索性能已经是线性的了同样的关键字集合有可能导致不同的树结构索引所以使用BST树还要考虑尽可能让BST树保持左图的结构和避免右图的结构也就是所谓的“平衡”问题平衡二叉树AVL Tree平衡树(Balance TreeBT) 定义平衡树(Balance TreeBT) 指的是任意节点的子树的高度差都小于等于1。常见的符合平衡树的有B树多路平衡搜索树、AVL树二叉平衡搜索树等。平衡树可以完成集合的一系列操作, 时间复杂度和空间复杂度相对于“2-3树”要低在完成集合的一系列操作中始终保持平衡为大型数据库的组织、索引提供了一条新的途径。特点所有节点的左右子树的高度差小于1的二叉树。如下图根节点左边高度是3因为左边最多有3条边右边高度而2相差1.根节点左边的节点50的左边是1条边高度为1右边有两条边高度为2相差1。红黑树Red-Black Tree定义红黑树Red Black Tree 是一种自平衡二叉搜索树是在计算机科学中用到的一种数据结构典型的用途是实现关联数组.红黑树是一种特化的AVL树平衡二叉树都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡从而获得较高的查找性能.特点节点是红色或黑色性质2. 根节点是黑色所有叶子都是黑色。叶子是NUIL节点每个红色节点的两个子节点都是黑色。从每个叶子到根的所有路径上不能有两个连续的红色节点从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点分析:红黑树会主动平衡树的结构,使树两边数据尽量达到平衡.始终保证左子节点数 父节点数 右子节点数的规则。但 红黑树 在大数据场景下面,树的高度不可控,那么存在叶子节点的数据,查找起来效率不会特别高.会多次IO读取磁盘中的数据(索引一般保存在磁盘当中).应用广泛用于C的STL中,map和set都是用红黑树实现的.著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间.IO多路复用epoll的实现采用红黑树组织管理sockfd以支持快速的增删改查.ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器.java中TreeMap的实现.