本文共 2226 字，大约阅读时间需要 7 分钟。
数据结构
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
二叉树（Binary Tree）
定义
二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树
特点
- 二叉树是每个节点最多有两个子节点的树
- 二叉树的叶子节点有0个字节点，二叉树的根节点或者内部节点有一个或者两个字节点。
相关术语
①结点：包含一个数据元素及若干指向子树分支的信息 。
②结点的度：一个结点拥有子树的数目称为结点的度 。 ③叶子结点：也称为终端结点，没有子树的结点或者度为零的结点 。 ④分支结点：也称为非终端结点，度不为零的结点称为非终端结点 。 ⑤树的度：树中所有结点的度的最大值 。 ⑥结点的层次：从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层 。 ⑦树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度 。 ⑧有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树 。 ⑨无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树 。 ⑩森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根结点删除，则该树就变成了一片森林，森林中的树由原来根结点的各棵子树构成 。二叉搜索树（Binary Search Tree）
定义
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。
特点
一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树； （4）没有键值相等的结点。
BST树的搜索
从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字.
如果BST树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变BST树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；
右边也是一个BST树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的树结构索引；所以，使用BST树还要考虑尽可能让BST树保持左图的结构，和避免右图的结构，也就是所谓的“平衡”问题； 平衡二叉树（AVL Tree）
平衡树(Balance Tree，BT) 定义
平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于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的实现.
转载地址：http://mnmo.baihongyu.com/