logo头像

待到风起时,扬帆济沧海

伸展树(SplayTree)

伸展树介绍伸展树(Splay Tree)是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。(01) 伸展树属于二叉查找树,即它具有和二叉查找树一样的性...

AVL树

AVL树介绍AVL树是高度平衡的而二叉树。它的特点是:AVL树中任何节点的两个子树的高度最大差别为1。上面的两张图片,左边的是AVL树,它的任何节点的两个子树的高度差别都<=1;而右边的不是AVL树,因为7的两颗子树的高度相差为...

红黑树

红-黑树的概念上一篇二叉搜索树,二叉搜索树对于某个节点而言,其左子树的节点关键值都小于该节点关键值,右子树的所有节点关键值都大于该节点关键值。二叉搜索树作为一种数据结构,其查找、插入和删除操作的时间复杂度都为O(logn),底数为2。...

二叉树

树的基本概念 树(tree)是一种抽象数据类型(ADT),用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点通过连接它们的边组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上...