1、 概述

二叉查找樹（Binary Search Tree，也叫二叉排序樹，即Binary Sort Tree）能夠支持多種動態集合操作，它可以用來表示有序集合、建立索引等，因而在實際應用中，二叉排序樹是一種非常重要的數據結構。

從算法復雜度角度考慮，我們知道，作用于二叉查找樹上的基本操作（如查找，插入等）的時間復雜度與樹的高度成正比。對一個含n個節點的完全二叉樹，這些操作的最壞情況運行時間為O(log n)。但如果因為頻繁的刪除和插入操作，導致樹退化成一個n個節點的線性鏈（此時即為一個單鏈表），則這些操作的最壞情況運行時間為O(n)。為了克服以上缺點，很多二叉查找樹的變形出現了，如紅黑樹、AVL樹，Treap樹等。

本文介紹了二叉查找樹的一種改進數據結構