数据结构与算法: 扩展树(Splay)
作用于二叉查找树上的基本操作(如查找,插入等)的时间复杂度与树的高度成正比。对一个含 n
个节点的完全二叉树,这些操作的最坏情况运行时间为 O(log n)
。但如果因为频繁的删除和插入操作,导致树退化成一个 n
个节点的线性链(此时即为一个单链表),则这些操作的最坏情况运行时间为 O(n)
。为了克服以上缺点,很多二叉查找树的变形出现了,如红黑树
、AVL树
,Treap树
等。
作用于二叉查找树上的基本操作(如查找,插入等)的时间复杂度与树的高度成正比。对一个含 n
个节点的完全二叉树,这些操作的最坏情况运行时间为 O(log n)
。但如果因为频繁的删除和插入操作,导致树退化成一个 n
个节点的线性链(此时即为一个单链表),则这些操作的最坏情况运行时间为 O(n)
。为了克服以上缺点,很多二叉查找树的变形出现了,如红黑树
、AVL树
,Treap树
等。
之前我们讲到 二叉搜索树
,从二叉搜索树到 2-3树
到 红黑树
到 B-树
。
学习过了二叉查找树,想必大家有遇到一个问题。例如,将一个数组 {1,2,3,4}
依次插入树的时候,形成了如下(a)的情况。有建立树与没建立树对于数据的增删查改已经没有了任何帮助,反而增添了维护的成本。而只有建立的树如下(b),才能够最大地体现二叉树的优点。
本篇文章中,我们将介绍常见的树形结构及其常用操作的运算复杂度。
raymondCaptain 2017.11.02
2013年09月20日 16:01:26 zolalad
2017年07月14日 17:24:32 浮生忆梦
张晓龙 2016.11.22
Go的错误处理一直被吐槽太繁琐, 作为主要用GO的攻城狮, 经常写 if err!=nil
, 但是如果想偷懒, 少带了上下文信息, 直接写 if err!=nil { return err}
或者 fmt.Errorf
携带的上下文信息太少了的话, 看到错误日志也会一脸懵逼, 难以定位问题.
**2016年04月29日 / elian **
在接触 redis 之前,相信很多人都有 mysql 的使用经验。
今天来分享一下Redis几道常见的面试题:
1、什么是Redis?