簡介

二元搜索樹(Binary Search Tree)是基於二元樹的一種延伸,二元搜索樹的應用範圍很廣,可以利用在搜索、排序和提供資料集合基本結構,發展其他資料結構,所以也是重要的資料結構之一。

定義

定義除了繼承二元樹的定義外,二元搜索樹本身也有額外的定義,但可能會看到幾種不同的說法,而較多數人使用的定義如下:

  1. 左子樹不為空,則左子樹的所有節點的鍵值(Key)小於根節點的鍵值。
  2. 右子樹不為空,則右子樹的所有節點的鍵值(Key)大於根節點的鍵值。
  3. 左右子樹也都是二元搜索樹。
  4. 節點不會有重複的鍵值。

這個定義是樹中的節點都具有Key-value pair情況,有時候可能會其他變化:

  1. 沒有鍵值,而用值(Value)來比較。
  2. 允許重複的資料,此時會出現等於的情況,則將定義1.改成小於等於或者定義2.改成大於等於。

以下為示意圖:

binary_search_tree  

實作

不同類型的樹會有不同的介面,原始版本通常會實作以下介面:

  1. add: 加入資料。(或insert)
  2. remove: 移除資料。(或delete)
  3. containsKey: 判斷是否包含鍵值。
  4. get: 取出資料。

無鍵值的版本則會有以下介面:

  1. add: 加入資料。(或insert)
  2. remove: 移除資料。(或delete)
  3. contains: 判斷是否包含資料。

本文將實作有鍵值版本,另外這邊也實作一些其他的介面:

  1. clone: 複製樹。
  2. size: 資料的數目。

刪除

刪除的操作較為複雜,作為資料集合時,刪除不能直接把節點與其子孫全部移除,而需要進行一些移動的操作讓樹保持二元搜索樹的定義,基本上有三種情況需要考慮:

  1. 沒有子節點時,可以直接移除。
  2. 有一個子節點時,將子節點取代被移除的節點的位置。
  3. 有兩個子節點時,將樹作中序(in-order)排列後,可以選擇被移除節點的前驅(predecessor)節點或後繼(successor)節點來替換;或者白話一點的說法,可以從左子樹找到最大值或右子樹找到最小值的節點,來取代被移除的節點位置,並同時將找到的節點之子節點取代自身的位置。

利用上面的示意圖來做說明,假設移除節點9,為有一個子節點的情況,所以把子節點7移上來取代,如下圖所示:

binary_search_tree_remove1  

而假設移除節點4,則為兩個子節點的情況,則可以選擇左子樹最大值,也就是節點3,或者右子樹最小值,也就是節點5來取代,這邊選擇節點5,如圖所示:

binary_search_tree_remove2  

而節點5有子節點6,子節點6取代原來節點5的位置,節點5則取代節點4的位置。這類情況可以用這張圖來說明:

574px-Binary_search_tree_delete_svg  

這張圖為移除節點7時,可以選擇節點6或9的調整方式。二元搜索樹的最大值就在最右邊的節點(搜索直到右子節點為空)最小值就在最左邊的節點(搜索直到左子節點為空),所以選擇左邊的情況,節點6一定不會有右子節點,反之節點9亦然,但可能會有一個子節點,必須移動到原來節點6或9的位置。

實作上可以用連結串列或者是陣列的方式來實作:

連結串列

連結串列的方式較為簡單,使用三個指標分別指向父節點、左子節點和右子節點即可完成。

陣列

實作上利用一個陣列來表示整棵樹的資料結構,利用索引公式來找到父節點、左子節點和右子節點,而無需另外的指標表示,可參考二元樹這篇文章。當樹不平衡時,會需要產生非常巨大的陣列,很容易就出現記憶體不足的現象,又加上刪除節點時需要重新調整陣列的元素位置很多,實作上不容易效能也較差,所以一般使用連結串列的方式實作較好。

語法

C#

抽象類別

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinarySearchTree
{
    public abstract class BinarySearchTree<K, V> where K : IComparable
    {
        public abstract int Count { get; }
        public abstract void Add(K key, V value);
        public abstract void Remove(K key);
        public abstract V Get(K key);
        public abstract bool ContainsKey(K key);
        public abstract BinarySearchTree<K, V> Clone();
    }
}

連結串列

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinarySearchTree
{
    public class LinkedBinarySearchTree<K, V> : BinarySearchTree<K, V> where K : IComparable
    {
        public class LinkedBinarySearchTreeNode<NK, NV> where NK : IComparable
        {
            public NK Key { get; set; }
            public NV Value { get; set; }
            public LinkedBinarySearchTreeNode<NK, NV> Parent { get; set; }
            public LinkedBinarySearchTreeNode<NK, NV> Left { get; set; }
            public LinkedBinarySearchTreeNode<NK, NV> Right { get; set; }

            public LinkedBinarySearchTreeNode(NK key, NV value)
            {
                Key = key;
                Value = value;
            }
        }

        protected LinkedBinarySearchTreeNode<K, V> root;
        protected int count;

        public override int Count
        {
            get
            {
                return count;
            }
        }

        public override void Add(K key, V value)
        {
            if (root == null)
                root = new LinkedBinarySearchTreeNode<K, V>(key, value);
            else
            {
                LinkedBinarySearchTreeNode<K, V> node = root;
                LinkedBinarySearchTreeNode<K, V> parent = null;
                int result = 0;
                while (node != null)
                {
                    result = key.CompareTo(node.Key);
                    parent = node;
                    if (result > 0)
                        node = node.Right;
                    else if (result < 0)
                        node = node.Left;
                    else
                    {
                        node.Value = value;
                        return;
                    }
                }
                LinkedBinarySearchTreeNode<K, V> child = new LinkedBinarySearchTreeNode<K, V>(key, value);
                child.Parent = parent;
                if (result > 0)
                    parent.Right = child;
                else
                    parent.Left = child;
            }
            ++count;
        }

        public override void Remove(K key)
        {
            LinkedBinarySearchTreeNode<K, V> node = Find(key);
            if (node == null)
                return;
            if (node.Left == null)
            {
                if (node.Right == null)
                    Replace(node, null);
                else
                    Replace(node, node.Right);
            }
            else if (node.Right == null)
                Replace(node, node.Left);
            else
            {
                LinkedBinarySearchTreeNode<K, V> tmpNode = node.Right;
                while (true)
                {
                    if (tmpNode.Left == null)
                        break;
                    tmpNode = tmpNode.Left;
                }
                Replace(tmpNode, tmpNode.Right);
                tmpNode.Left = node.Left;
                if (node.Left != null)
                    node.Left.Parent = tmpNode;
                tmpNode.Right = node.Right;
                if (node.Right != null)
                    node.Right.Parent = tmpNode;
                Replace(node, tmpNode);
            }
            --count;
        }

        public override V Get(K key)
        {
            LinkedBinarySearchTreeNode<K, V> node = Find(key);
            if(node == null)
                throw new KeyNotFoundException();
            return node.Value;
        }

        public override bool ContainsKey(K key)
        {
            return Find(key) != null;
        }

        protected void Replace(LinkedBinarySearchTreeNode<K, V> node, LinkedBinarySearchTreeNode<K, V> newNode)
        {
            LinkedBinarySearchTreeNode<K, V> parent = node.Parent;
            if (parent != null)
            {
                if (node == parent.Left)
                    parent.Left = newNode;
                else
                    parent.Right = newNode;
                node.Parent = null;
            }
            else
                root = newNode;

            if (newNode != null)
                newNode.Parent = parent;

            node.Left = null;
            node.Right = null;
        }

        protected LinkedBinarySearchTreeNode<K, V> Find(K key)
        {
            LinkedBinarySearchTreeNode<K, V> node = root;
            while (node != null)
            {
                int result = key.CompareTo(node.Key);
                if (result > 0)
                    node = node.Right;
                else if (result < 0)
                    node = node.Left;
                else
                    break;
            }
            return node;
        }

        public override BinarySearchTree<K, V> Clone()
        {
            LinkedBinarySearchTree<K, V> cloneTree = new LinkedBinarySearchTree<K, V>();
            cloneTree.root = new LinkedBinarySearchTreeNode<K, V>(root.Key, root.Value);
            CloneChildren(cloneTree.root, root);
            cloneTree.count = count;
            return cloneTree;
        }

        protected void CloneChildren(LinkedBinarySearchTreeNode<K, V> cloneNode, LinkedBinarySearchTreeNode<K, V> node)
        {
            LinkedBinarySearchTreeNode<K, V> tmpNode = node.Left;
            LinkedBinarySearchTreeNode<K, V> tmpCloneNode;
            if (tmpNode != null)
            {
                tmpCloneNode = new LinkedBinarySearchTreeNode<K, V>(tmpNode.Key, tmpNode.Value);
                tmpCloneNode.Parent = cloneNode;
                cloneNode.Left = tmpCloneNode;
                CloneChildren(tmpCloneNode, tmpNode);
            }

            tmpNode = node.Right;
            if (tmpNode != null)
            {
                tmpCloneNode = new LinkedBinarySearchTreeNode<K, V>(tmpNode.Key, tmpNode.Value);
                tmpCloneNode.Parent = cloneNode;
                cloneNode.Right = tmpCloneNode;
                CloneChildren(tmpCloneNode, tmpNode);
            }
        }
    }
}

陣列

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinarySearchTree
{
    public class ArrayBinarySearchTree<K, V> : BinarySearchTree<K, V> where K : IComparable
    {
        public class ArrayBinarySearchTreeNode<NK, NV> where NK : IComparable
        {
            public NK Key { get; set; }
            public NV Value { get; set; }
            public ArrayBinarySearchTreeNode(NK key, NV value)
            {
                Key = key;
                Value = value;
            }
        }

        protected ArrayBinarySearchTreeNode<K, V>[] array;
        protected int count;

        public override int Count
        {
            get
            {
                return count;
            }
        }
        
        public ArrayBinarySearchTree()
            : this(10240)
        {
        }

        public ArrayBinarySearchTree(int capacity)
        {
            array = new ArrayBinarySearchTreeNode<K, V>[capacity];
        }

        public override void Add(K key, V value)
        {
            int length = array.Length;
            int index = 1;
            while (array[index] != null)
            {
                int result = key.CompareTo(array[index].Key);
                if (result > 0)
                    index = index * 2 + 1;
                else if (result < 0)
                    index = index * 2;
                else
                {
                    array[index].Value = value;
                    return;
                }

                if (index + 1 > length)
                {
                    ArrayBinarySearchTreeNode<K, V>[] newArray = new ArrayBinarySearchTreeNode<K, V>[length * 2];
                    Array.Copy(array, newArray, length);
                    array = newArray;
                    length *= 2;
                }
            }
            array[index] = new ArrayBinarySearchTreeNode<K, V>(key, value);
            ++count;
        }

        public override void Remove(K key)
        {
            int index = IndexOf(key);
            if (index == -1)
                return;

            int length = array.Length;
            int leftIndex = index * 2;
            int rightIndex = leftIndex + 1;
            if (leftIndex >= length || array[leftIndex] == null)
            {
                if (rightIndex >= length || array[rightIndex] == null)
                    array[index] = null;
                else
                    MoveTree(rightIndex, index);
            }
            else if (rightIndex >= length || array[rightIndex] == null)
                MoveTree(leftIndex, index);
            else
            {
                // find left-max or right-min node;
                int tmpIndex = rightIndex * 2;
                while (tmpIndex < length && array[tmpIndex] != null)
                    tmpIndex *= 2;
                tmpIndex /= 2;
                array[index] = array[tmpIndex];
                MoveTree(tmpIndex * 2 + 1, tmpIndex);
            }
            --count;
        }

        public override V Get(K key)
        {
            int index = IndexOf(key);
            if (index == -1)
                throw new KeyNotFoundException();
            return array[index].Value;
        }

        public override bool ContainsKey(K key)
        {
            return IndexOf(key) != -1;
        }

        protected int IndexOf(K key)
        {
            int length = array.Length;
            int index = 1;
            while (index < length && array[index] != null)
            {
                int result = key.CompareTo(array[index].Key);
                if (result > 0)
                    index = index * 2 + 1;
                else if (result < 0)
                    index = index * 2;
                else
                    return index;
            }
            return -1;
        }

        protected void MoveTree(int from, int to)
        {
            Queue<KeyValuePair<int, int>> queue = new Queue<KeyValuePair<int, int>>();
            queue.Enqueue(new KeyValuePair<int, int>(from, to));
            while (queue.Count > 0)
            {
                KeyValuePair<int, int> pair = queue.Dequeue();
                int f = pair.Key;
                int t = pair.Value;
                if (Move(f, t))
                {
                    queue.Enqueue(new KeyValuePair<int, int>(f * 2, t * 2));
                    queue.Enqueue(new KeyValuePair<int, int>(f * 2 + 1, t * 2 + 1));
                }
            }
        }

        protected bool Move(int from, int to)
        {
            // from > to
            int length = array.Length;
            if (from < length)
            {
                if (array[from] == null)
                {
                    array[to] = null;
                    return false;
                }
                array[to] = array[from];
                array[from] = null;
                return true;
            }
            else if (to < length)
                array[to] = null;
            return false;
        }

        public override BinarySearchTree<K, V> Clone()
        {
            ArrayBinarySearchTree<K, V> cloneTree = new ArrayBinarySearchTree<K, V>(array.Length);
            for (int i = 1; i < array.Length; ++i)
                if (array[i] != null)
                    cloneTree.array[i] = new ArrayBinarySearchTreeNode<K, V>(array[i].Key, array[i].Value);
            cloneTree.count = count;
            return cloneTree;
        }
    }
}

Java

抽象類別

public abstract class BinarySearchTree<K extends Comparable<K>, V> {
    public abstract int size();
    public abstract void add(K key, V value);
    public abstract void remove(K key);
    public abstract V get(K key);
    public abstract boolean containsKey(K key);
    public abstract BinarySearchTree<K, V> copy();
}

連結串列

public class LinkedBinarySearchTree<K extends Comparable<K>, V> extends BinarySearchTree<K, V> {
	public static class LinkedBinarySearchTreeNode<NK, NV>
    {
        public NK key;
        public NV value;
        public LinkedBinarySearchTreeNode<NK, NV> parent;
        public LinkedBinarySearchTreeNode<NK, NV> left;
        public LinkedBinarySearchTreeNode<NK, NV> right;

        public LinkedBinarySearchTreeNode(NK key, NV value)
        {
            this.key = key;
            this.value = value;
        }
    }

    protected LinkedBinarySearchTreeNode<K, V> root;
    protected int size;

	@Override
	public int size() {
		return size;
	}

	@Override
	public void add(K key, V value) {
		if (root == null)
			root = new LinkedBinarySearchTreeNode<K, V>(key, value);
        else
        {
            LinkedBinarySearchTreeNode<K, V> node = root;
            LinkedBinarySearchTreeNode<K, V> parent = null;
            int result = 0;
            while (node != null)
            {
                result = key.compareTo(node.key);
                parent = node;
                if (result > 0)
                    node = node.right;
                else if (result < 0)
                    node = node.left;
                else
                {
                    node.value = value;
                    return;
                }
            }
            LinkedBinarySearchTreeNode<K, V> child = new LinkedBinarySearchTreeNode<K, V>(key, value);
            child.parent = parent;
            if (result > 0)
                parent.right = child;
            else
                parent.left = child;
        }
        ++size;
	}

	@Override
	public void remove(K key) {
		LinkedBinarySearchTreeNode<K, V> node = find(key);
        if (node == null)
            return;
        if (node.left == null)
        {
            if (node.right == null)
                replace(node, null);
            else
                replace(node, node.right);
        }
        else if (node.right == null)
            replace(node, node.left);
        else
        {
            LinkedBinarySearchTreeNode<K, V> tmpNode = node.right;
            while (true)
            {
                if (tmpNode.left == null)
                    break;
                tmpNode = tmpNode.left;
            }
            replace(tmpNode, tmpNode.right);
            tmpNode.left = node.left;
            if (node.left != null)
                node.left.parent = tmpNode;
            tmpNode.right = node.right;
            if (node.right != null)
                node.right.parent = tmpNode;
            replace(node, tmpNode);
        }
        --size;
	}

	@Override
	public V get(K key) {
        LinkedBinarySearchTreeNode<K, V> node = find(key);
        if(node == null)
            return null;
        return node.value;
	}

	@Override
	public boolean containsKey(K key) {
		return find(key) != null;
	}

	@Override
	public BinarySearchTree<K, V> copy() {
		LinkedBinarySearchTree<K, V> cloneTree = new LinkedBinarySearchTree<K, V>();
        cloneTree.root = new LinkedBinarySearchTreeNode<K, V>(root.key, root.value);
        cloneChildren(cloneTree.root, root);
        cloneTree.size = size;
        return cloneTree;
	}

    protected void replace(LinkedBinarySearchTreeNode<K, V> node, LinkedBinarySearchTreeNode<K, V> newNode)
    {
        LinkedBinarySearchTreeNode<K, V> parent = node.parent;
        if (parent != null)
        {
            if (node == parent.left)
                parent.left = newNode;
            else
                parent.right = newNode;
            node.parent = null;
        }
        else
        	root = newNode;

        if (newNode != null)
            newNode.parent = parent;

        node.left = null;
        node.right = null;
    }

    protected LinkedBinarySearchTreeNode<K, V> find(K key)
    {
        LinkedBinarySearchTreeNode<K, V> node = root;
        while (node != null)
        {
            int result = key.compareTo(node.key);
            if (result > 0)
                node = node.right;
            else if (result < 0)
                node = node.left;
            else
                break;
        }
        return node;
    }
    
    protected void cloneChildren(LinkedBinarySearchTreeNode<K, V> cloneNode, LinkedBinarySearchTreeNode<K, V> node)
    {
        LinkedBinarySearchTreeNode<K, V> tmpNode = node.left;
        LinkedBinarySearchTreeNode<K, V> tmpCloneNode;
        if (tmpNode != null)
        {
            tmpCloneNode = new LinkedBinarySearchTreeNode<K, V>(tmpNode.key, tmpNode.value);
            tmpCloneNode.parent = cloneNode;
            cloneNode.left = tmpCloneNode;
            cloneChildren(tmpCloneNode, tmpNode);
        }

        tmpNode = node.right;
        if (tmpNode != null)
        {
            tmpCloneNode = new LinkedBinarySearchTreeNode<K, V>(tmpNode.key, tmpNode.value);
            tmpCloneNode.parent = cloneNode;
            cloneNode.right = tmpCloneNode;
            cloneChildren(tmpCloneNode, tmpNode);
        }
    }
}

陣列

import java.util.AbstractMap.SimpleEntry;
import java.util.LinkedList;
import java.util.Queue;


public class ArrayBinarySearchTree<K extends Comparable<K>, V> extends BinarySearchTree<K, V> {
	public static class ArrayBinarySearchTreeNode<NK, NV>
    {
        public NK key;
        public NV value;
        public ArrayBinarySearchTreeNode(NK key, NV value)
        {
            this.key = key;
            this.value = value;
        }
    }
	
	protected ArrayBinarySearchTreeNode<K, V>[] array;
	protected int size;

    public ArrayBinarySearchTree()
    {
    	this(10240);
    }
    
    @SuppressWarnings("unchecked")
    public ArrayBinarySearchTree(int capacity)
    {
        this.array = (ArrayBinarySearchTreeNode<K, V>[])new ArrayBinarySearchTreeNode[capacity];
    }
    
	@Override
	public int size() {
		return size;
	}

	@SuppressWarnings("unchecked")
	@Override
	public void add(K key, V value) {
		int length = array.length;
        int index = 1;
        while (array[index] != null)
        {
            int result = key.compareTo(array[index].key);
            if (result > 0)
                index = index * 2 + 1;
            else if (result < 0)
                index = index * 2;
            else
            {
                array[index].value = value;
                return;
            }

            if (index + 1 > length)
            {
            	ArrayBinarySearchTreeNode<K, V>[] newArray = (ArrayBinarySearchTreeNode<K, V>[])new ArrayBinarySearchTreeNode[array.length * 2];
                System.arraycopy(array, 0, newArray, 0, array.length);
                array = newArray;
                length *= 2;
            }
        }
        array[index] = new ArrayBinarySearchTreeNode<K, V>(key, value);
        ++size;
	}

	@Override
	public void remove(K key) {
		int index = indexOf(key);
        if (index == -1)
            return;

        int length = array.length;
        int leftIndex = index * 2;
        int rightIndex = leftIndex + 1;
        if (leftIndex >= length || array[leftIndex] == null)
        {
            if (rightIndex >= length || array[rightIndex] == null)
                array[index] = null;
            else
                moveTree(rightIndex, index);
        }
        else if (rightIndex >= length || array[rightIndex] == null)
        	moveTree(leftIndex, index);
        else
        {
            // find left-max or right-min node;
            int tmpIndex = rightIndex * 2;
            while (tmpIndex < length && array[tmpIndex] != null)
                tmpIndex *= 2;
            tmpIndex /= 2;
            array[index] = array[tmpIndex];
            moveTree(tmpIndex * 2 + 1, tmpIndex);
        }
        --size;
	}

	@Override
	public V get(K key) {
		int index = indexOf(key);
        if (index == -1)
        	return null;
        return array[index].value;
	}

	@Override
	public boolean containsKey(K key) {
		return indexOf(key) != -1;
	}

	@Override
	public BinarySearchTree<K, V> copy() {
		ArrayBinarySearchTree<K, V> cloneTree = new ArrayBinarySearchTree<K, V>(array.length);
        for (int i = 1; i < array.length; ++i)
            if (array[i] != null)
                cloneTree.array[i] = new ArrayBinarySearchTreeNode<K, V>(array[i].key, array[i].value);
        cloneTree.size = size;
        return cloneTree;
	}

    protected int indexOf(K key)
    {
        int length = array.length;
        int index = 1;
        while (index < length && array[index] != null)
        {
            int result = key.compareTo(array[index].key);
            if (result > 0)
                index = index * 2 + 1;
            else if (result < 0)
                index = index * 2;
            else
                return index;
        }
        return -1;
    }

    protected void moveTree(int from, int to)
    {
        Queue<SimpleEntry<Integer, Integer>> queue = new LinkedList<SimpleEntry<Integer, Integer>>();
        queue.add(new SimpleEntry<Integer, Integer>(from, to));
        while (queue.size() > 0)
        {
        	SimpleEntry<Integer, Integer> entry = queue.poll();
            int f = entry.getKey();
            int t = entry.getValue();
            if (move(f, t))
            {
            	queue.add(new SimpleEntry<Integer, Integer>(f * 2, t * 2));
            	queue.add(new SimpleEntry<Integer, Integer>(f * 2 + 1, t * 2 + 1));
            }
        }
    }

    protected boolean move(int from, int to)
    {
        // from > to
        int length = array.length;
        if (from < length)
        {
            if (array[from] == null)
            {
                array[to] = null;
                return false;
            }
            array[to] = array[from];
            array[from] = null;
            return true;
        }
        else if (to < length)
            array[to] = null;
        return false;
    }

}

C++

抽象類別

#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H

template<typename K, typename V>
class BinarySearchTree
{
    public:
        virtual int size() = 0;
        virtual void add(K key, V value) = 0;
        virtual void remove(K key) = 0;
        virtual V get(K key) = 0;
        virtual bool containsKey(K key) = 0;
        virtual BinarySearchTree<K, V>* clone() = 0;
    protected:
        int compareTo(K key1, K key2)
        {
            if(key1 > key2)
                return 1;
            else if(key1 < key2)
                return -1;
            return 0;
        }
    private:
};

#endif // BINARYSEARCHTREE_H

連結串列

#ifndef LINKEDBINARYSEARCHTREE_H
#define LINKEDBINARYSEARCHTREE_H

#include "BinarySearchTree.h"

template<typename K, typename V>
class LinkedBinarySearchTreeNode;

template<typename K, typename V>
class LinkedBinarySearchTree : public BinarySearchTree<K, V>
{
    public:
        LinkedBinarySearchTree()
        {
            root = 0;
            _size = 0;
        }
        virtual ~LinkedBinarySearchTree()
        {
            if(root != 0)
                delete root;
        }

        int size()
        {
            return _size;
        }

        void add(K key, V value)
        {
            if (root == 0)
                root = new LinkedBinarySearchTreeNode<K, V>(key, value);
            else
            {
                LinkedBinarySearchTreeNode<K, V>* node = root;
                LinkedBinarySearchTreeNode<K, V>* parent = 0;
                int result = 0;
                while (node != 0)
                {
                    result = BinarySearchTree<K, V>::compareTo(key, node->key);
                    parent = node;
                    if (result > 0)
                        node = node->right;
                    else if (result < 0)
                        node = node->left;
                    else
                    {
                        node->value = value;
                        return;
                    }
                }
                LinkedBinarySearchTreeNode<K, V>* child = new LinkedBinarySearchTreeNode<K, V>(key, value);
                child->parent = parent;
                if (result > 0)
                    parent->right = child;
                else
                    parent->left = child;
            }
            ++_size;
        }

        void remove(K key)
        {
            LinkedBinarySearchTreeNode<K, V>* node = find(key);
            if (node == 0)
                return;
            if (node->left == 0)
            {
                if (node->right == 0)
                    replace(node, 0);
                else
                    replace(node, node->right);
            }
            else if (node->right == 0)
                replace(node, node->left);
            else
            {
                LinkedBinarySearchTreeNode<K, V>* tmpNode = node->right;
                while (true)
                {
                    if (tmpNode->left == 0)
                        break;
                    tmpNode = tmpNode->left;
                }
                replace(tmpNode, tmpNode->right);
                tmpNode->left = node->left;
                if (node->left != 0)
                    node->left->parent = tmpNode;
                tmpNode->right = node->right;
                if (node->right != 0)
                    node->right->parent = tmpNode;
                replace(node, tmpNode);
            }
            delete node;
            --_size;
        }

        V get(K key)
        {
            LinkedBinarySearchTreeNode<K, V>* node = find(key);
            if(node == 0)
                throw "Key not found";
            return node->value;
        }

        bool containsKey(K key)
        {
            return find(key) != 0;
        }

        BinarySearchTree<K, V>* clone()
        {
            LinkedBinarySearchTree<K, V>* cloneTree = new LinkedBinarySearchTree<K, V>();
            cloneTree->root = new LinkedBinarySearchTreeNode<K, V>(root->key, root->value);
            cloneChildren(cloneTree->root, root);
            cloneTree->_size = _size;
            return cloneTree;
        }
    protected:
        LinkedBinarySearchTreeNode<K, V>* root;
        int _size;

        void replace(LinkedBinarySearchTreeNode<K, V>* node, LinkedBinarySearchTreeNode<K, V>* newNode)
        {
            LinkedBinarySearchTreeNode<K, V>* parent = node->parent;
            if (parent != 0)
            {
                if (node == parent->left)
                    parent->left = newNode;
                else
                    parent->right = newNode;
                node->parent = 0;
            }
            else
                root = newNode;

            if (newNode != 0)
                newNode->parent = parent;

            node->left = 0;
            node->right = 0;
        }

        LinkedBinarySearchTreeNode<K, V>* find(K key)
        {
            LinkedBinarySearchTreeNode<K, V>* node = root;
            while (node != 0)
            {
                int result = BinarySearchTree<K, V>::compareTo(key, node->key);
                if (result > 0)
                    node = node->right;
                else if (result < 0)
                    node = node->left;
                else
                    break;
            }
            return node;
        }

        void cloneChildren(LinkedBinarySearchTreeNode<K, V>* cloneNode, LinkedBinarySearchTreeNode<K, V>* node)
        {
            LinkedBinarySearchTreeNode<K, V>* tmpNode = node->left;
            LinkedBinarySearchTreeNode<K, V>* tmpCloneNode;
            if (tmpNode != 0)
            {
                tmpCloneNode = new LinkedBinarySearchTreeNode<K, V>(tmpNode->key, tmpNode->value);
                tmpCloneNode->parent = cloneNode;
                cloneNode->left = tmpCloneNode;
                cloneChildren(tmpCloneNode, tmpNode);
            }

            tmpNode = node->right;
            if (tmpNode != 0)
            {
                tmpCloneNode = new LinkedBinarySearchTreeNode<K, V>(tmpNode->key, tmpNode->value);
                tmpCloneNode->parent = cloneNode;
                cloneNode->right = tmpCloneNode;
                cloneChildren(tmpCloneNode, tmpNode);
            }
        }
    private:
};

template<typename K, typename V>
class LinkedBinarySearchTreeNode
{
    public:
        LinkedBinarySearchTreeNode(K key, V value)
        {
            this->key = key;
            this->value = value;
            parent = 0;
            left = 0;
            right = 0;
        }
        //virtual ~ArrayBinarySearchTreeNode();
        K key;
        V value;
        LinkedBinarySearchTreeNode<K, V>* parent;
        LinkedBinarySearchTreeNode<K, V>* left;
        LinkedBinarySearchTreeNode<K, V>* right;
    protected:
    private:
};
#endif // LINKEDBINARYSEARCHTREE_H

陣列

#ifndef ARRAYBINARYSEARCHTREE_H
#define ARRAYBINARYSEARCHTREE_H

#include <memory.h>
#include <queue>
#include "BinarySearchTree.h"

using namespace std;

template<typename K, typename V>
class ArrayBinarySearchTreeNode;

template<typename K, typename V>
class ArrayBinarySearchTree : public BinarySearchTree<K, V>
{
    public:
        ArrayBinarySearchTree(int capacity = 10240)
        {
            array = new ArrayBinarySearchTreeNode<K, V>*[capacity];
            for(int i = 1;i < capacity;++i)
                array[i] = 0;
            _size = 0;
            arrayLength = capacity;
        }
        virtual ~ArrayBinarySearchTree()
        {
            for(int i = 0;i < arrayLength;++i)
                delete array[i];
            delete [] array;
        }

        int size()
        {
            return _size;
        }

        void add(K key, V value)
        {
            int index = 1;
            while (array[index] != 0)
            {
                int result = BinarySearchTree<K, V>::compareTo(key, array[index]->key);
                if (result > 0)
                    index = index * 2 + 1;
                else if (result < 0)
                    index = index * 2;
                else
                {
                    array[index]->value = value;
                    return;
                }

                if (index + 1 > arrayLength)
                {
                    int newLength = arrayLength * 2;
                    ArrayBinarySearchTreeNode<K, V>** newArray = new ArrayBinarySearchTreeNode<K, V>*[newLength];
                    memcpy(newArray, array, arrayLength * sizeof(ArrayBinarySearchTreeNode<K, V>*));
                    delete [] array;
                    array = newArray;
                    for(int i = arrayLength;i < newLength;++i)
                        array[i] = 0;
                    arrayLength *= 2;
                }
            }
            array[index] = new ArrayBinarySearchTreeNode<K, V>(key, value);
            ++_size;
        }

        void remove(K key)
        {
            int index = indexOf(key);
            if (index == -1)
                return;

            ArrayBinarySearchTreeNode<K, V>* node = array[index];
            int leftIndex = index * 2;
            int rightIndex = leftIndex + 1;
            if (leftIndex >= arrayLength || array[leftIndex] == 0)
            {
                if (rightIndex >= arrayLength || array[rightIndex] == 0)
                    array[index] = 0;
                else
                    moveTree(rightIndex, index);
            }
            else if (rightIndex >= arrayLength || array[rightIndex] == 0)
                moveTree(leftIndex, index);
            else
            {
                // find left-max or right-min node;
                int tmpIndex = rightIndex * 2;
                while (tmpIndex < arrayLength && array[tmpIndex] != 0)
                    tmpIndex *= 2;
                tmpIndex /= 2;
                array[index] = array[tmpIndex];
                moveTree(tmpIndex * 2 + 1, tmpIndex);
            }
            delete node;
            --_size;
        }

        V get(K key)
        {
            int index = indexOf(key);
            if (index == -1)
                throw "Key not found";
            return array[index]->value;
        }

        bool containsKey(K key)
        {
            return indexOf(key) != -1;
        }

        BinarySearchTree<K, V>* clone()
        {
            ArrayBinarySearchTree<K, V>* cloneTree = new ArrayBinarySearchTree<K, V>(arrayLength);
            for (int i = 1; i < arrayLength; ++i)
                if (array[i] != 0)
                    cloneTree->array[i] = new ArrayBinarySearchTreeNode<K, V>(array[i]->key, array[i]->value);
            cloneTree->_size = _size;
            return cloneTree;
        }
    protected:
        ArrayBinarySearchTreeNode<K, V>** array;
        int arrayLength;
        int _size;

        int indexOf(K key)
        {
            int index = 1;
            while (index < arrayLength && array[index] != 0)
            {
                int result = BinarySearchTree<K, V>::compareTo(key, array[index]->key);
                if (result > 0)
                    index = index * 2 + 1;
                else if (result < 0)
                    index = index * 2;
                else
                    return index;
            }
            return -1;
        }

        void moveTree(int from, int to)
        {
            queue<int*> queue;
            int* pair = new int[2];
            pair[0] = from;
            pair[1] = to;
            queue.push(pair);
            while (queue.size() > 0)
            {
                pair = queue.front();
                queue.pop();
                int f = pair[0];
                int t = pair[1];
                delete [] pair;
                if (move(f, t))
                {
                    pair = new int[2];
                    pair[0] = f * 2;
                    pair[1] = t * 2;
                    queue.push(pair);
                    pair = new int[2];
                    pair[0] = f * 2 + 1;
                    pair[1] = t * 2 + 1;
                    queue.push(pair);
                }
            }
        }

        bool move(int from, int to)
        {
            // from > to
            if (from < arrayLength)
            {
                if (array[from] == 0)
                {
                    array[to] = 0;
                    return false;
                }
                array[to] = array[from];
                array[from] = 0;
                return true;
            }
            else if (to < arrayLength)
                array[to] = 0;
            return false;
        }
    private:
};

template<typename K, typename V>
class ArrayBinarySearchTreeNode
{
    public:
        ArrayBinarySearchTreeNode(K key, V value)
        {
            this->key = key;
            this->value = value;
        }
        K key;
        V value;
    protected:
    private:
};
#endif // ARRAYBINARYSEARCHTREE_H

隨機產生1000筆資料執行結果(因為資料不平衡,陣列很容易就記憶體不足,只跑1000筆):

C#
Add LinkedBinarySearchTree Time: 10ms
Memory uage: 28304bytes
Validate: True
Remove LinkedBinarySearchTree Time: 0ms
Add ArrayBinarySearchTree Time: 30ms
Memory uage: 10460800bytes
Validate: True
Remove ArrayBinarySearchTree Time: 0ms

Java
Add LinkedBinarySearchTree Time: 0ms
Validate: true
Remove LinkedBinarySearchTree Time: 0ms
Add ArrayBinarySearchTree Time: 10ms
Validate: true
Remove ArrayBinarySearchTree Time: 10ms

C++
Add LinkedBinarySearchTree Time: 0ms
Validate: 1
Remove LinkedBinarySearchTree Time: 0ms
Add ArrayBinarySearchTree Time: 50ms
Validate: 1
Remove ArrayBinarySearchTree Time: 0ms

下載

VS2010 C#版本

Eclipse Java版本

Code::Blocks C++版本

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()