分类: 计算机科学

红黑树

与数组相比,链表提升了插入元素的效率。因为数组在插入元素时,需要移动后续元素的位置;而链表只需要改变后继元素的 prev 属性。然而在查询元素时,链表需要遍历所有元素,并不高效。借助于红黑树,既能提升查询的效率,又能保证插入的效率。 为什么说红黑树有助于提升查询和插入的效率呢?因为红黑树本质上是一棵完美平衡的二叉查找树,可以通过节点的有序性保证查找和插入操作的便捷,其作时间复杂度就是树的高度 O(

代理模式

概述代理模式(proxy pattern) 的主要处理逻辑为,构建代理对象以桥接对实际对象的访问。因此,可以在访问过程中构建附加的间接性操作如请求处理、权限校验、内务处理(housekeeping task)等,也可以为多种实际对象提供统一的接口。 《设计模式:可复用面向对象软件的基础》中的说法是: Provide a surrogate or placeholder for another ob

职责链模式

概述职责链模式(Chain of Responsibility)的主要实现逻辑为,将请求的处理对象构造为链式结构,然后在这条链上依序传递请求,直到请求被某个对象处理,或者最终得不到处理。 《设计模式:可复用面向对象软件的基础》一书将职责链模式描述为: Avoid coupling the sender of a request to its receiver by giving morethan

策略模式

概述状态模式(Strategy pattern,也称为算法簇模式)的主要实现逻辑为,构建多个策略类用于封装不同的算法,并将这些算法的其中一个以引用形式注入给上下文对象,以使上下文对象可以将其行为委托给策略类处理。相较于状态模式内部封装了状态切换,上下文对象的行为多数委托给状态对象加以处理,策略模式委托给策略类的处理通常只是单个行为,即算法,并且,设置策略(即替换算法)的过程由外部调用者完成。 《设

状态模式

概述状态模式(State pattern) 的主要处理逻辑为,构建多个状态对象(state object)以维护特定状态下的行为集,和一个上下文对象(context)以引用形式维护与当前状态对应的状态对象,并将与状态相关的行为委托给这个状态对象加以处理;当状态更新时,上下文对象将重设其实际引用的状态对象,而其行为也将得到变更。通常,状态以标识符形式(有时候表现为内部数据值,即除了标识符以外,还有额

观察者模式

概述观察者模式(Observer pattern)也称为发布-订阅模式(publish-subscribe pattern),其处理逻辑即是当主题对象(a subject or a observable,也称为目标)的状态发生变更时,自动以广播的形式通知依赖于它的多个观察者(observers),促使这些观察者执行后续的动作。其一般意义即为,在一对多的依赖关系中,当依赖更新时,所有依赖于它的对象(