树的种类:


B树 二叉搜索树(二叉排序树)

满二叉树: 节点树n=2的k次方-1, 每个树的节点要么是0要么是2. 

完全二叉树, 除了最后一层以外的节点都是满节点, 最后一层的叶子都集中在最左边。

B+树

B-树

B*树

AVL树

Splay树(伸展树):

红黑树

Treap树:为B树添加了优先级概念, 引入了堆的性质。 性能在B树与AVL之间。

Trie树(字典树、前缀树):把26个字母、数字作为子树的根节点, 依次向下扩展。 可用于词频统计、前缀匹配

Huffman哈夫曼树:权重路径最优

构建方法:最低权重的树在最末端, 依次向上建




常规则查找:

1. 遍历, 时间复杂度O(n) 

2. 在排序数组里二分查找 O(log2N) 

3. 链式存储, 二叉排序树 O(log2N) 

4. 哈希, O(1) 


AVL树 二叉平衡树特性:

1. 只分左树右树和根节点

2. 左右两树的 最大深度差是1

3.左树的值永远小于右树,  根节点的值永远小于右节点并 大于左节点


当平衡树不平衡时, 进行旋转:

0. 先从最底层向上找失恒的节点. 

1. 对最底层的失恒节点进行旋转,再依次向上旋转

2. 方法:右右左旋、左左右旋、右左旋、右左旋

3. 树如果需要删除, 一般不物理删除, 只置一个标志位


实现:

1. 找到插入位置

2. 平衡

3. 



你可能感兴趣的