赞
踩
特性:整棵树只能有一个树根,节点间不可交叉和成环。
特点:
在树的基础上,
每个节点上最多有两个子节点
特点:
在二叉树的基础上,
有序。即在每棵子树中,均有:左子节点的值<根节点的值<右子节点的值。
特点:
在二叉搜索树的基础上,
自平衡。即在当有新的节点加入或旧的节点删除时,会通过一些节点的旋转,自动调节树的结构,使树保持平衡的结构,以保持较高的查询效率。
特点:
在自平衡二叉搜索树的基础上,
有颜色。即通过与颜色相关的《红黑树5性质》限定了红黑树自平衡的程度,使其不是严格意义上的平衡二叉树。平衡二叉树过于严格的限制了高度差不得超过1,会使树的结构调整过于频繁。这也是为什么要有红黑树。
方法:
所谓前序遍历,就是根节点在前面访问,左节点始终哎右节点前访问。所以是:根->左子->右子
特点:
所谓中序遍历,就是根节点在中间访问,左节点始终哎右节点前访问。所以是:左子->根->右子
方法:
所谓后序遍历,就是根节点后访问,左节点始终哎右节点前访问。所以是:左子->右子->根
左支尽头的叶子节点为最小值。即从根节点出发一直沿着左子节点找,直到没有左子节点,到达的叶子节点则为该二叉搜索树(红黑树也是一样)的最小值所在的节点。
右支尽头的叶子节点为最大值。即从根节点出发一直沿着右子节点找,直到没有右子节点,到达的叶子节点则为该二叉搜索树(红黑树也是一样)的最大值所在的节点。
将其父节点指向该节点的引用改为指向null即可。该节点从引用链上脱离,即会在GC时被回收。
子节点直接取而代之。
后继节点:比某个节点的值大的最小节点。
使用被删节点的后继节点替换被删节点。
设从N个元素中查找一个元素最坏情况需要K次查到,查到即剩余待查询的元素数量为1.
则有:N/(2^K)=1
变换得:K=log2(N)
所以,时间复杂度为:O(log2(N)) ==> O(logN)
无论是左旋还是右旋,都是一个“逆转”的过程,即一逆二转。
过程:
逆:一个关系线(原子树根节点与新子树根节点之间的)变为原来的逆向;
转:
一个关系线(新子树根节点与其原左子节点之间的)将起点向左转到原子树根节点上,
一个关系线(原子树的根节点与其父节点之间的)将终点向右旋转到新子树根节点上
过程:
逆:一个关系线(原子树根节点与新子树根节点之间的)变为原来的逆向;
转:
一个关系线(新子树根节点与其原右子节点之间的)将起点向右转到原子树根节点上,
一个关系线(原子树的根节点与其父节点之间的)将终点向左旋转到新子树根节点上
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。