树结构基础篇


基本概念

  • 二叉树:深度指当前节点距离根节点唯一路径的长;高度指当前节点距离树叶节点最长路径的长。
  • 二叉查找树:任何一个节点,左子树的值小于它,右子树的值大于它
  • 平衡二叉树(AVL树):树的深度必须为lgN,N为节点个数;或者说任何一个节点,保证它的左右子树的高度差不大于1
  • M叉树
  • B+树

应用

  1. 有序数组转二叉查找树,二叉查找树转有序数组;
  2. 二叉查找树转AVL(平衡)二叉查找树,使用单旋转或双旋转;

    单旋转:左-左/右-右——当某个节点(相对的根节点)的左儿子增加左子树,引起原AVL树不平衡时,将左儿子节点拎起来,即上移至相对根节点的层级,即深度减一,相对根节点重新排布;右-右的情况类似。
    双旋转:左-右/右-左——当某个节点(相对的根节点)的左儿子增加右子树,引起原AVL树不平衡时,将右子树节点拎起来,即上移至相对根节点的层级,即深度减二,相对根节点重新排布;右-左的情况类似。

这篇博文写的很好:图解二叉树搜索算法


作者:闪光之歌,发布于:2019/05/16
原文:https://www.cnblogs.com/jacktao/p/10874217.html