Tree

概念

树是图的子集,是一种一定有一个根节点(root)的无环图。

Binary Tree

Binary Search Tree

二叉查找树(BST): 要么是一颗空树,否则对于任意节点

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值
  3. 任意节点的左、右子树也分别为二叉查找树
  4. 没有键值相等的节点。

中序遍历二叉查找树可得到一个关键字的有序序列,一个无序序列可以通过构造一棵二叉查找树变成一个有序序列,构造树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点,在进行插入操作时,不必移动其它结点,只需改动某个结点的指针,由空变为非空即可。搜索、插入、删除的复杂度等于树高,期望O(log n),最坏O(n)(数列有序,树退化成线性表)。

Self-Balancing Binary Search Tree

平衡二叉搜索树: 任意节点的左子树的高度差不超过1的二叉搜索树。常见的平衡二叉搜索树有AVL TreeRed-Black TreeTreap节点大小平衡树

AVL Tree

红黑树

B Tree

衍生自Self-Balancing Binary Search Tree,但是不同的是,B树是多路的(一个节点可以有2个以上的子节点)。B树是一种自平衡的树,并且保持数据有序,能够让查找数据、顺序访问、插入数据及删除的动作,都在对数时间内完成。B树非常适合于读写存储在存储系统(如磁盘)中的相对较大的数据块,所以它通常用于数据库和文件系统中,例如 MongoDB。

B+ Tree

B+ Tree是一种多路查询树,它的查询速度与树的高度有关,即O(log n)

为什么 MySQL 数据库要用B+树存储索引

qin

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码支持
扫码打赏

打开支付宝扫一扫,即可进行扫码打赏哦