数据结构 - 树和二叉树

二叉树

二叉树二叉树特点是每个结点最多只能有两棵子树且有左右之分。

存储结构使用数组存储存储时按先序遍历存储优点是层次和度与数组的索引存在对应关系2的n次方+度

完全二叉树

满二叉树
二叉树的存储结构
如果一棵二叉树只有度为0的结点和度为2的结点并且度为0的结点在同一层上则这棵二叉树为满二叉树

二叉搜索树

二叉搜索树是一棵二叉有序树保证左子树上所有节点小于根节点的值而右子树上所有节点的值都大于根节点的值。

树在平衡条件下的查询效率达到O(log2N),极端非平衡条件下查找效率退化到O(N)
若任意节点的左子树不为空则左子树上所有节点的值均小于它的根节点的值
若任意节点的右子树不为空则右子树上所有节点的值均大于它的根节点的值
任意节点的左、右子树也分别为二叉查找树
没有键值相等的节点
前序遍历【DLR】前序遍历也叫先根遍历先访问根节点然后遍历左子树最后遍历右子树
中序遍历【LDR】中序遍历也叫中根遍历先遍历左子树然后访问根节点最后遍历右子树
后序遍历【LRD】后序遍历也叫后根遍历先遍历左子树然后遍历右子树最后访问根节点

平衡二叉树

最优二叉树

哈夫曼树Huffman

B+ Tree

数据结构可视化
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

B+树的特点
每个树的节点只存放键值不存放数值而由叶子节点存放数值。这样数节点的度比较大而高度比较低从而有利于提高查询效率。
叶子节点存放数值并按照大小顺序排序且带指向相邻节点的指针以便高效地进行区间查询。
B+树的更新操作不从根节点开始而是从叶子节点开始。

日志结构合并树LSM

参考https://blog.csdn.net/zmm0420/article/details/123751580