摘要： 1. 紅黑樹的概念 紅黑樹從平衡二叉搜索樹延伸出來(lái)的一種較為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，它會(huì)對(duì)樹的各個(gè)節(jié)點(diǎn)進(jìn)行著色標(biāo)記（紅色和黑色），相對(duì)于AVL樹來(lái)說(shuō)，犧牲了部分平衡性以換取插入/刪除操作時(shí)少量的旋轉(zhuǎn)操作，（插入最多需要旋轉(zhuǎn)2次，刪除最多需要旋轉(zhuǎn)3次），整體來(lái)說(shuō)性能要優(yōu)于AVL樹。在插入和刪除操作的時(shí)候依據(jù)節(jié) 閱讀全文

摘要： 1. 二叉搜索樹 二叉搜索樹又稱二叉排序樹，他的左子樹上的節(jié)點(diǎn)都小于根節(jié)點(diǎn)，他的右子樹上的節(jié)點(diǎn)都大于根節(jié)點(diǎn)，每一個(gè)左右子樹又是一個(gè)二叉搜索樹 2. 刪除節(jié)點(diǎn)的幾種情況： 3. 二叉搜索樹的實(shí)現(xiàn)： # 構(gòu)建節(jié)點(diǎn)類 class BiTreeNode: def __init__(self, item): 閱讀全文

摘要： 1. AVL樹的概念 AVL樹又稱為高度搜索樹，它是一個(gè)特殊的二叉搜索樹，當(dāng)元素接近于有序的時(shí)候，二叉樹也會(huì)變成一個(gè)單鏈樹，所以AVL樹就是平衡二叉搜索樹，當(dāng)插入一個(gè)節(jié)點(diǎn)，樹的任意一個(gè)左右子樹的高度差都<=1，稱為AVL樹 上圖左邊的二叉樹的每個(gè)節(jié)點(diǎn)的左右子樹的最大高度差都不超過1，而右邊的二叉樹的 閱讀全文