首页 > 其他分享 >各种树

各种树

时间:2022-10-20 18:47:48浏览次数:93  
标签:各种 tree 二叉 子树 二叉树 平衡 节点

1 满二叉树(full tree)

 

 

 

 

 

 

2 完全二叉树 (complete tree)

 

  特点:从上到下从左到右编号,编号能连续。

3 二叉搜索树(二叉查找树,二叉排序树) (binary search tree, BST)

 

 

 

 

 特点:左子树的所有节点都小于根节点,右子树的所有节点都不小于根节点;子树也分别为二叉搜索树。

查找时,类似二分法,最优是O(logN)。最差是O(N),如下一条腿特别长,需要挨个遍历:

 

 

4 二叉平衡树(AVL,平衡二叉搜索树)

优化了二叉搜索树,防止出现一条腿特别长的情况。

特点:左右子树高度差不超过1;子树也是二叉平衡树。

 

 (二叉平衡树不一定是完全二叉树,如上图)

插入节点的时候,为了保持平衡,会进行旋转,这部分可以参考:AVL Tree | Set 1 (Insertion) - GeeksforGeeks 或者 平衡二叉树_清风拂来水波不兴的博客-CSDN博客_平衡二叉树

标签:各种,tree,二叉,子树,二叉树,平衡,节点
From: https://www.cnblogs.com/zxq89/p/16810869.html

相关文章