知乎鏈接：http://www.zhihu.com/question/19604641

1.什么是arc被丧？（arc是為了解決什么問題誕生的糖儡？）

首先解釋ARC: automatic reference counting自動引用計數(shù)。
ARC幾個要點：
在對象被創(chuàng)建時 retain count +1埋涧，在對象被release時 retain count -1.當retain count 為0 時，銷毀對象戏羽。
程序中加入autoreleasepool的對象會由系統(tǒng)自動加上autorelease方法梧奢，如果該對象引用計數(shù)為0狱掂，則銷毀。
那么ARC是為了解決什么問題誕生的呢亲轨？這個得追溯到MRC手動內(nèi)存管理時代說起趋惨。
MRC下內(nèi)存管理的缺點：
1.當我們要釋放一個堆內(nèi)存時，首先要確定指向這個堆空間的指針都被release了惦蚊。（避免提前釋放）
2.釋放指針指向的堆空間器虾，首先要確定哪些指針指向同一個堆，這些指針只能釋放一次蹦锋。（MRC下即誰創(chuàng)建兆沙，誰釋放，避免重復釋放）
3.模塊化操作時莉掂，對象可能被多個模塊創(chuàng)建和使用葛圃，不能確定最后由誰去釋放。
4.多線程操作時憎妙，不確定哪個線程最后使用完畢

2.請解釋以下keywords的區(qū)別： assign vs weak, __block vs __weak

assign適用于基本數(shù)據(jù)類型库正，weak是適用于NSObject對象，并且是一個弱引用厘唾。
assign其實也可以用來修飾對象褥符，那么我們?yōu)槭裁床挥盟兀恳驗楸籥ssign修飾的對象在釋放之后阅嘶，指針的地址還是存在的属瓣，也就是說指針并沒有被置為nil。如果在后續(xù)的內(nèi)存分配中讯柔，剛好分到了這塊地址抡蛙，程序就會崩潰掉。
而weak修飾的對象在釋放之后魂迄，指針地址會被置為nil粗截。所以現(xiàn)在一般弱引用就是用weak。
首先__block是用來修飾一個變量捣炬，這個變量就可以在block中被修改（參考block實現(xiàn)原理）
__block：使用__block修飾的變量在block代碼快中會被retain（ARC下熊昌，MRC下不會retain）
__weak：使用__weak修飾的變量不會在block代碼塊中被retain
同時，在ARC下湿酸，要避免block出現(xiàn)循環(huán)引用 __weak typedof(self)weakSelf = self;

3.__block在arc和非arc下含義一樣嗎婿屹？

是不一樣的。
在MRC中__block variable在block中使用是不會retain的
但是ARC中__block則是會Retain的推溃。
取而代之的是用__weak或是__unsafe_unretained來更精確的描述weak reference的目的
其中前者只能在iOS5之後可以使用昂利，但是比較好 (該物件release之後，此pointer會自動設成nil)
而後者是ARC的環(huán)境下為了相容4.x的解決方案。
所以上面的範例中

 __block MyClass* temp = …;    // MRC環(huán)境下使用
 __weak MyClass* temp = …;    // ARC但只支援iOS5.0以上的版本
 __unsafe_retained MyClass* temp = …;  //ARC且可以相容4.x以後的版本

4.使用nonatomic一定是線程安全的嗎蜂奸？（）

不是的犁苏。
atomic原子操作，系統(tǒng)會為setter方法加鎖扩所。 具體使用 @synchronized(self){//code }
nonatomic不會為setter方法加鎖围详。
atomic：線程安全，需要消耗大量系統(tǒng)資源來為屬性加鎖
nonatomic：非線程安全祖屏，適合內(nèi)存較小的移動設備

5.描述一個你遇到過的retain cycle例子助赞。

block中的循環(huán)引用：一個viewController

    @property (nonatomic,strong)HttpRequestHandler * handler;
    @property (nonatomic,strong)NSData          *data;
    _handler = [httpRequestHandler sharedManager];
    [ downloadData:^(id responseData){
        _data = responseData;
    }];

self 擁有_handler, _handler 擁有block, block擁有self（因為使用了self的_data屬性，block會copy 一份self）
解決方法：

    __weak typedof(self)weakSelf = self
    [ downloadData:^(id responseData){
        weakSelf.data = responseData;
    }];

6.+(void)load; +(void)initialize袁勺；有什么用處嫉拐？

在Objective-C中，runtime會自動調(diào)用每個類的兩個方法魁兼。+load會在類初始加載時調(diào)用，+initialize會在第一次調(diào)用類的類方法或?qū)嵗椒ㄖ氨徽{(diào)用漠嵌。這兩個方法是可選的咐汞，且只有在實現(xiàn)了它們時才會被調(diào)用。
共同點：兩個方法都只會被調(diào)用一次儒鹿。

7.為什么其他語言里叫函數(shù)調(diào)用化撕， objective c里則是給對象發(fā)消息（或者談下對runtime的理解）

先來看看怎么理解發(fā)送消息的含義：

曾經(jīng)覺得Objc特別方便上手，面對著 Cocoa 中大量 API约炎，只知道簡單的查文檔和調(diào)用植阴。還記得初學 Objective-C 時把[receiver message]當成簡單的方法調(diào)用，而無視了“發(fā)送消息”這句話的深刻含義圾浅。于是[receiver message]會被編譯器轉(zhuǎn)化為：
objc_msgSend(receiver, selector)
如果消息含有參數(shù)掠手，則為：
objc_msgSend(receiver, selector, arg1, arg2, ...)

如果消息的接收者能夠找到對應的selector，那么就相當于直接執(zhí)行了接收者這個對象的特定方法狸捕；否則喷鸽，消息要么被轉(zhuǎn)發(fā)，或是臨時向接收者動態(tài)添加這個selector對應的實現(xiàn)內(nèi)容灸拍，要么就干脆玩完崩潰掉做祝。

現(xiàn)在可以看出[receiver message]真的不是一個簡簡單單的方法調(diào)用。因為這只是在編譯階段確定了要向接收者發(fā)送message這條消息鸡岗，而receive將要如何響應這條消息混槐，那就要看運行時發(fā)生的情況來決定了。

Objective-C 的 Runtime 鑄就了它動態(tài)語言的特性轩性，這些深層次的知識雖然平時寫代碼用的少一些声登，但是卻是每個 Objc 程序員需要了解的。

Objc Runtime使得C具有了面向?qū)ο竽芰Γ诔绦蜻\行時創(chuàng)建捌刮，檢查碰煌，修改類、對象和它們的方法绅作÷可以使用runtime的一系列方法實現(xiàn)。

順便附上OC中一個類的數(shù)據(jù)結(jié)構 /usr/include/objc/runtime.h

   struct objc_class {
    Class isa OBJC_ISA_AVAILABILITY; //isa指針指向Meta Class俄认，因為Objc的類的本身也是一個Object个少，為了處理這個關系，r       untime就創(chuàng)造了Meta Class眯杏，當給類發(fā)送[NSObject alloc]這樣消息時夜焦，實際上是把這個消息發(fā)給了Class Object

    #if !__OBJC2__
    Class super_class OBJC2_UNAVAILABLE; // 父類
    const char *name OBJC2_UNAVAILABLE; // 類名
    long version OBJC2_UNAVAILABLE; // 類的版本信息，默認為0
    long info OBJC2_UNAVAILABLE; // 類信息岂贩，供運行期使用的一些位標識
    long instance_size OBJC2_UNAVAILABLE; // 該類的實例變量大小
    struct objc_ivar_list *ivars OBJC2_UNAVAILABLE; // 該類的成員變量鏈表
    struct objc_method_list **methodLists OBJC2_UNAVAILABLE; // 方法定義的鏈表
    struct objc_cache *cache OBJC2_UNAVAILABLE; // 方法緩存茫经，對象接到一個消息會根據(jù)isa指針查找消息對象，這時會在method       Lists中遍歷萎津，如果cache了卸伞，常用的方法調(diào)用時就能夠提高調(diào)用的效率。
    struct objc_protocol_list *protocols OBJC2_UNAVAILABLE; // 協(xié)議鏈表
    #endif

    } OBJC2_UNAVAILABLE;

OC中一個類的對象實例的數(shù)據(jù)結(jié)構（/usr/include/objc/objc.h）:

    typedef struct objc_class *Class;

    /// Represents an instance of a class.

    struct objc_object {

        Class isa  OBJC_ISA_AVAILABILITY;

    };

    /// A pointer to an instance of a class.

    typedef struct objc_object *id;

向object發(fā)送消息時锉屈，Runtime庫會根據(jù)object的isa指針找到這個實例object所屬于的類荤傲，然后在類的方法列表以及父類方法列表尋找對應的方法運行。id是一個objc_object結(jié)構類型的指針颈渊，這個類型的對象能夠轉(zhuǎn)換成任何一種對象遂黍。

然后再來看看消息發(fā)送的函數(shù)：objc_msgSend函數(shù)

在引言中已經(jīng)對objc_msgSend進行了一點介紹，看起來像是objc_msgSend返回了數(shù)據(jù)俊嗽，其實objc_msgSend從不返回數(shù)據(jù)而是你的方法被調(diào)用后返回了數(shù)據(jù)雾家。下面詳細敘述下消息發(fā)送步驟：

檢測這個 selector 是不是要忽略的。比如 Mac OS X 開發(fā)绍豁，有了垃圾回收就不理會 retain,release 這些函數(shù)了榜贴。
檢測這個 target 是不是 nil 對象。ObjC 的特性是允許對一個 nil 對象執(zhí)行任何一個方法不會 Crash妹田，因為會被忽略掉唬党。
如果上面兩個都過了，那就開始查找這個類的 IMP鬼佣，先從 cache 里面找驶拱，完了找得到就跳到對應的函數(shù)去執(zhí)行。
如果 cache 找不到就找一下方法分發(fā)表晶衷。
如果分發(fā)表找不到就到超類的分發(fā)表去找蓝纲，一直找阴孟，直到找到NSObject類為止。
如果還找不到就要開始進入動態(tài)方法解析了税迷，后面會提到永丝。

后面還有：
動態(tài)方法解析resolveThisMethodDynamically
消息轉(zhuǎn)發(fā)forwardingTargetForSelector

詳情可參考我的第一篇文章。

8.什么是method swizzling?

Method Swizzling 原理（方法混淆箭养？）

在Objective-C中調(diào)用一個方法慕嚷，其實是向一個對象發(fā)送消息，查找消息的唯一依據(jù)是selector的名字毕泌。利用Objective-C的動態(tài)特性喝检，可以實現(xiàn)在運行時偷換selector對應的方法實現(xiàn)，達到給方法掛鉤的目的撼泛。
每個類都有一個方法列表，存放著selector的名字和方法實現(xiàn)的映射關系愿题。IMP有點類似函數(shù)指針潘酗，指向具體的Method實現(xiàn)撩炊。

方法指向

我們可以利用 method_exchangeImplementations 來交換2個方法中的IMP，

我們可以利用 class_replaceMethod 來修改類崎脉，

我們可以利用 method_setImplementation 來直接設置某個方法的IMP伯顶，
……
歸根結(jié)底，都是偷換了selector的IMP祭衩，如下圖所示：

方法交換

詳情：http://blog.csdn.net/yiyaaixuexi/article/details/9374411

9.UIView和CALayer是啥關系灶体？

1.UIView是iOS系統(tǒng)中界面元素的基礎，所有的界面元素都繼承自它蝎抽。它本身完全是由CoreAnimation來實現(xiàn)的 （Mac下似乎不是這樣）路克。它真正的繪圖部分，是由一個叫CALayer（Core Animation Layer）的類來管理瓢宦。 UIView本身灰羽，更像是一個CALayer的管理器鱼辙，訪問它的跟繪圖和跟坐標有關的屬性玫镐，例如frame恐似，bounds等 等，實際上內(nèi)部都是在訪問它所包含的CALayer的相關屬性葱椭。

2.UIView有個layer屬性口四，可以返回它的主CALayer實例，UIView有一個layerClass方法治笨，返回主layer所使用的 類赤嚼，UIView的子類，可以通過重載這個方法等孵，來讓UIView使用不同的CALayer來顯示蹂空，例如通過

    - (class) layerClass {

         return ([CAEAGLLayer class]);
    }

=使某個UIView的子類使用GL來進行繪制上枕。

3.UIView的CALayer類似UIView的子View樹形結(jié)構，也可以向它的layer上添加子layer棋恼，來完成某些特殊的表 示锈玉。例如下面的代碼

    grayCover = [[CALayer alloc] init];

    grayCover.backgroundColor = [[[UIColor blackColor] colorWithAlphaComponent:0.2] CGColor];

    [self.layer addSubLayer: grayCover];

會在目標View上敷上一層黑色的透明薄膜拉背。

4.UIView的layer樹形在系統(tǒng)內(nèi)部，被系統(tǒng)維護著三份copy（這段理解有點吃不準）抡诞。

1. 邏輯樹，就是代碼里可以操縱的肴熏，例如更改layer的屬性等等就在這一份顷窒。
2. 動畫樹，這是一個中間層鸦做，系統(tǒng)正在這一層上更改屬性谓着，進行各種渲染操作赊锚。
3. 顯示樹，這棵樹的內(nèi)容是當前正被顯示在屏幕上的內(nèi)容耸袜。

這三棵樹的邏輯結(jié)構都是一樣的牲平，區(qū)別只有各自的屬性。

10. 如何高性能的給UIImageView加個圓角蜈抓？（不準說layer.cornerRadius!）

我覺得應該是使用Quartz2D直接繪制圖片,得把這個看看。
步驟：
　　a酬土、創(chuàng)建目標大小(cropWidth撤缴，cropHeight)的畫布。

b微宝、使用UIImage的drawInRect方法進行繪制的時候虎眨，指定rect為(-x镶摘，-y凄敢，width湿痢，height)。

c拒逮、從畫布中得到裁剪后的圖像滩援。

- (UIImage*)cropImageWithRect:(CGRect)cropRect
{
    CGRect drawRect = CGRectMake(-cropRect.origin.x , -cropRect.origin.y, self.size.width * self.scale, self.size.height * self.scale);
    
    UIGraphicsBeginImageContext(cropRect.size);
    CGContextRef context = UIGraphicsGetCurrentContext();
    CGContextClearRect(context, CGRectMake(0, 0, cropRect.size.width, cropRect.size.height));
    
    [self drawInRect:drawRect];
    
    UIImage *image = UIGraphicsGetImageFromCurrentImageContext();
    UIGraphicsEndImageContext();
    
    return image;
}
@end

另外也看到其他朋友的方法以现，使用貝塞爾曲線來切割圖片：

imageView.center = CGPointMake(200, 300);  
UIImage *anotherImage = [UIImage imageNamed:@"image"];  
UIGraphicsBeginImageContextWithOptions(imageView.bounds.size, NO, 1.0);  
[[UIBezierPath bezierPathWithRoundedRect:imageView.bounds
                           cornerRadius:50] addClip];
[anotherImage drawInRect:imageView.bounds];
imageView.image = UIGraphicsGetImageFromCurrentImageContext();  
UIGraphicsEndImageContext();  
[self.view addSubview:imageView];

11. 使用drawRect有什么影響邑遏？（這個可深可淺，你至少得用過憎蛤。纪吮。）

drawRect方法依賴Core Graphics框架來進行自定義的繪制篮灼，但這種方法主要的缺點就是它處理touch事件的方式：每次按鈕被點擊后冰肴，都會用setNeddsDisplay進行強制重繪；而且不止一次联逻，每次單點事件觸發(fā)兩次執(zhí)行检痰。這樣的話從性能的角度來說，對CPU和內(nèi)存來說都是欠佳的公壤。特別是如果在我們的界面上有多個這樣的UIButton實例境钟。

12. ASIHttpRequest或者SDWebImage里面給UIImageView加載圖片的邏輯是什么樣的？

詳見SDWebImage的實現(xiàn)流程 http://www.cnblogs.com/6duxz/p/4159572.html

13. 麻煩你設計個簡單的圖片內(nèi)存緩存器（移除策略是一定要說的）

圖片的內(nèi)存緩存洞渔，可以考慮將圖片數(shù)據(jù)保存到一個數(shù)據(jù)模型中缚态。所以在程序運行時這個模型都存在內(nèi)存中玫芦。
移除策略：釋放數(shù)據(jù)模型對象。

14. 講講你用Instrument優(yōu)化動畫性能的經(jīng)歷吧（別問我什么是Instrument）

可以參考iOS App性能優(yōu)化

15. loadView是干嘛用的医增？

當你訪問一個ViewController的view屬性時老虫，如果此時view的值是nil祈匙，那么，ViewController就會自動調(diào)用loadView這個方法跪帝。這個方法就會加載或者創(chuàng)建一個view對象些阅，賦值給view屬性市埋。
loadView默認做的事情是：如果此ViewController存在一個對應的nib文件，那么就加載這個nib聘裁。否則弓千，就創(chuàng)建一個UIView對象洋访。

如果你用Interface Builder來創(chuàng)建界面，那么不應該重載這個方法呆抑。

如果你想自己創(chuàng)建view對象汁展，那么可以重載這個方法食绿。此時你需要自己給view屬性賦值。你自定義的方法不應該調(diào)用super耀销。如果你需要對view做一些其他的定制操作铲汪，在viewDidLoad里面去做掌腰。

=========================================

根據(jù)上面的文檔可以知道，有兩種情況：

1转晰、如果你用了nib文件士飒，重載這個方法就沒有太大意義酵幕。因為loadView的作用就是加載nib。如果你重載了這個方法不調(diào)用super邓深，那么nib文件就不會被加載笔刹。如果調(diào)用了super舌菜，那么view已經(jīng)加載完了，你需要做的其他事情在viewDidLoad里面做更合適袱瓮。

2、如果你沒有用nib绊起，這個方法默認就是創(chuàng)建一個空的view對象虱歪。如果你想自己控制view對象的創(chuàng)建栅表，例如創(chuàng)建一個特殊尺寸的view，那么可以重載這個方法局装，自己創(chuàng)建一個UIView對象铐尚，然后指定 self.view = myView; 但這種情況也沒有必要調(diào)用super哆姻，因為反正你也不需要在super方法里面創(chuàng)建的view對象矛缨。如果調(diào)用了super，那么就是浪費了一些資源而已
參考：http://www.cnblogs.com/dyllove98/archive/2013/06/06/3123005.html

16. viewWillLayoutSubView你總是知道的灵妨。

橫豎屏切換的時候落竹，系統(tǒng)會響應一些函數(shù)述召，其中 viewWillLayoutSubviews 和 viewDidLayoutSubviews。

//

- (void)viewWillLayoutSubviews

{

     [self _shouldRotateToOrientation:(UIDeviceOrientation)[UIApplication sharedApplication].statusBarOrientation];

}

-(void)_shouldRotateToOrientation:(UIDeviceOrientation)orientation {
        if (orientation == UIDeviceOrientationPortrait ||orientation ==
                UIDeviceOrientationPortraitUpsideDown) {
          // 豎屏
}
else {
         // 橫屏
    }
}

通過上述一個函數(shù)就知道橫豎屏切換的接口了藤为。
注意：viewWillLayoutSubviews只能用在ViewController里面缅疟，在view里面沒有響應窿吩。

17. GCD里面有哪幾種Queue错览？你自己建立過串行queue嗎？背后的線程模型是什么樣的轧邪？

1.主隊列 dispatch_main_queue(); 串行 忌愚，更新UI
2.全局隊列 dispatch_global_queue(); 并行却邓，四個優(yōu)先級：background腊徙，low，default螟蝙，high
3.自定義隊列 dispatch_queue_t queue ; 可以自定義是并行：DISPATCH_QUEUE_CONCURRENT或者串行DISPATCH_QUEUE_SERIAL

18. 用過coredata或者sqlite嗎民傻？讀寫是分線程的嗎漓踢？遇到過死鎖沒？咋解決的碟刺？

參考：CoreData與SQLite的線程安全

19. http的post和get啥區(qū)別半沽？（區(qū)別挺多的吴菠，麻煩多說點）

1.GET請求的數(shù)據(jù)會附在URL之后（就是把數(shù)據(jù)放置在HTTP協(xié)議頭中）做葵，以?分割URL和傳輸數(shù)據(jù)，參數(shù)之間以&相連榨乎，如：login.action?name=hyddd&password=idontknow&verify=%E4%BD%A0%E5%A5%BD蜜暑。如果數(shù)據(jù)是英文字母/數(shù)字，原樣發(fā)送隐绵，如果是空格依许，轉(zhuǎn)換為+缀蹄，如果是中文/其他字符缺前，則直接把字符串用BASE64加密，得出如：%E4%BD%A0%E5%A5%BD滞欠，其中％XX中的XX為該符號以16進制表示的ASCII肆良。
　　POST把提交的數(shù)據(jù)則放置在是HTTP包的包體中惹恃。

2."GET方式提交的數(shù)據(jù)最多只能是1024字節(jié)，理論上POST沒有限制朗儒，可傳較大量的數(shù)據(jù)醉锄，IIS4中最大為80KB浙值，IIS5中為100KB"开呐？规求？阻肿！

以上這句是我從其他文章轉(zhuǎn)過來的丛塌，其實這樣說是錯誤的蛹找，不準確的：

(1).首先是"GET方式提交的數(shù)據(jù)最多只能是1024字節(jié)"庸疾，因為GET是通過URL提交數(shù)據(jù)当编，那么GET可提交的數(shù)據(jù)量就跟URL的長度有直接關系了忿偷。而實際上鲤桥，URL不存在參數(shù)上限的問題，HTTP協(xié)議規(guī)范沒有對URL長度進行限制嫂拴。這個限制是特定的瀏覽器及服務器對它的限制筒狠。IE對URL長度的限制是2083字節(jié)(2K+35)箱沦。對于其他瀏覽器谓形，如Netscape、FireFox等谁帕，理論上沒有長度限制匈挖，其限制取決于操作系統(tǒng)的支持。

注意這是限制是整個URL長度舶吗，而不僅僅是你的參數(shù)值數(shù)據(jù)長度誓琼。[見參考資料5]

(2).理論上講腹侣，POST是沒有大小限制的齿穗，HTTP協(xié)議規(guī)范也沒有進行大小限制窃页，說“POST數(shù)據(jù)量存在80K/100K的大小限制”是不準確的，POST數(shù)據(jù)是沒有限制的乒省，起限制作用的是服務器的處理程序的處理能力袖扛。

3.在ASP中攻锰，服務端獲取GET請求參數(shù)用Request.QueryString妓雾，獲取POST請求參數(shù)用Request.Form械姻。在JSP中楷拳，用request.getParameter("XXXX")來獲取，雖然jsp中也有request.getQueryString()方法陶耍，但使用起來比較麻煩她混，比如：傳一個test.jsp?name=hyddd&password=hyddd，用request.getQueryString()得到的是：name=hyddd&password=hyddd馒过。在PHP中腹忽，可以用$_GET和$_POST分別獲取GET和POST中的數(shù)據(jù)窘奏，而$_REQUEST則可以獲取GET和POST兩種請求中的數(shù)據(jù)葫录。值得注意的是压昼，JSP中使用request和PHP中使用$_REQUEST都會有隱患瘤运，這個下次再寫個文章總結(jié)。

4.POST的安全性要比GET的安全性高拯坟。注意：這里所說的安全性和上面GET提到的“安全”不是同個概念但金。上面“安全”的含義僅僅是不作數(shù)據(jù)修改，而這里安全的含義是真正的Security的含義郁季，比如：通過GET提交數(shù)據(jù)冷溃，用戶名和密碼將明文出現(xiàn)在URL上，因為(1)登錄頁面有可能被瀏覽器緩存梦裂，(2)其他人查看瀏覽器的歷史紀錄似枕，那么別人就可以拿到你的賬號和密碼了，除此之外年柠，使用GET提交數(shù)據(jù)還可能會造成Cross-site request forgery攻擊。

總結(jié)一下冗恨，Get是向服務器發(fā)索取數(shù)據(jù)的一種請求答憔，而Post是向服務器提交數(shù)據(jù)的一種請求，在FORM（表單）中掀抹，Method默認為"GET"虐拓，實質(zhì)上，GET和POST只是發(fā)送機制不同傲武，并不是一個取一個發(fā)蓉驹！

20. 我知道你大學畢業(yè)過后就沒接觸過算法數(shù)據(jù)結(jié)構了城榛，但是請你一定告訴我什么是Binary search tree? search的時間復雜度是多少？

Binary search tree:二叉搜索樹戒幔。
主要由四個方法：（用C語言實現(xiàn)或者Python）
1.search：時間復雜度為O(h)吠谢，h為樹的高度

2.traversal：時間復雜度為O(n)，n為樹的總結(jié)點數(shù)诗茎。

3.insert：時間復雜度為O(h)工坊，h為樹的高度。

4.delete：最壞情況下敢订，時間復雜度為O(h)+指針的移動開銷王污。

可以看到，二叉搜索樹的dictionary operation的時間復雜度與樹的高度h相關楚午。所以需要盡可能的降低樹的高度昭齐，由此引出平衡二叉樹Balanced binary tree。它要求左右兩個子樹的高度差的絕對值不超過1矾柜，并且左右兩個子樹都是一棵平衡二叉樹阱驾。這樣就可以將搜索樹的高度盡量減小。常用算法有紅黑樹怪蔑、AVL里覆、Treap、伸展樹等缆瓣。

Written with StackEdit.