紅黑樹
紅黑樹是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構。它是在1972年由Rudolf Bayer發明的，他稱之為"對稱二叉B樹"。它是複雜的，但它的操作有着良好的最壞情況運行時間，並且在實踐中是高效的: 它可以在O(log n)時間內做查找，插入和刪除，這裡的n 是樹中元素的數目。紅黑樹和AVL樹一樣都對插入時間、刪除時間和查找時間提供了最好可能的最壞情況擔保。這不只是使它們在時間敏感的應用如即時應用中有價值，而且使它們有在提供最壞情況擔保的其他數據結構中作為建造板塊的價值；例如，在計算幾何中使用的很多數據結構都可以基於紅黑樹。
