首页  

数据结构中的各种树     所属分类 DS 浏览量 312
二叉树
二叉查找树 BST Binary Search Tree  , left < root < right
二叉搜索树 退化成线性表 ,最坏情况 搜索时间复杂度 O(n) 

二叉平衡树 Balanced Binary Tree  AVL
由前苏联 数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树

解决 二叉搜索树 退化问题
任意节点的左右子树高度差不超过1

红黑树(RB Tree)是平衡二叉树

哈夫曼树 Huffman Tree 最优二叉树 带权路径长度最小的树  


trie树 Double Array 字典查找树
Trie树既可用于一般的字典搜索,也可用于索引查找

B树 
多路搜索树  
所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中

B+树 
在B树基础上,叶子结点增加链表指针
关键字存储在叶子结点,非叶子结点作为叶子结点的索引 

B*树
在B+树基础上,非叶子结点增加链表指针


注意 没有B-树 ,B-Tree 被翻译成B-树,其实就是B树

LSM Tree



B树与红黑树,为什么数据库使用B树索引 LSM Tree 要点整理

上一篇     下一篇
数据结构二元组

编程语言发展史

LLVM简介

树的定义和术语

算法基础知识

java String indexOf 为何不使用KMP