今天在課堂上我的教授說有一個平衡二叉搜索樹,我以前從來沒有聽說過。我想知道是否有沒有旋轉的平衡二進制搜索樹? 從我的理解來看,Balance Binary Search Tree是AVL樹。此外,我不認爲有可能建立一個'平衡二進制搜索樹'。 但是,如果有這樣的數據結構,我怎麼能從一系列隨機數字中構建一個「平衡二叉搜索樹」?關於二叉搜索樹的問題?
感謝,
今天在課堂上我的教授說有一個平衡二叉搜索樹,我以前從來沒有聽說過。我想知道是否有沒有旋轉的平衡二進制搜索樹? 從我的理解來看,Balance Binary Search Tree是AVL樹。此外,我不認爲有可能建立一個'平衡二進制搜索樹'。 但是,如果有這樣的數據結構,我怎麼能從一系列隨機數字中構建一個「平衡二叉搜索樹」?關於二叉搜索樹的問題?
感謝,
背後使用隨機數是像你這樣將增加節點的樹,它的鍵是隨機數填充平衡二叉樹的想法。當你實現一個平衡的二叉搜索樹時,用100或1000個具有隨機數的節點填充它。高度應儘可能小 - 這是平衡二叉搜索樹的關鍵特徵。
存在AVL樹以外的平衡二叉搜索樹(如紅黑樹)。用平衡二叉搜索樹搜索谷歌。
維基百科的樹木在任何樹有關的物品,例如http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
感謝Donotalo,我知道紅黑樹的底部,一個漂亮的列表。我的意思是除了所有的紅黑樹,AVL樹和2-3,2-3-4樹,有沒有'平衡二叉樹搜索'? 我認爲我的教授犯了一個錯誤,我不認爲有這樣的樹。通過從一個文件讀入一個數組,我可以對它進行排序,然後使用中點算法來構建一個平衡樹,但這棵樹確實是二叉樹,只是你插入數字的問題。他說,這個「平衡二叉搜索樹」的最壞情況是O(N),我認爲這也是一個錯誤。據我所知,一棵名爲「平衡」的樹必須有 – Chan 2010-08-26 05:05:07