二叉查找树

二叉查找树是具有有以下性质的二叉树：

1. 若左子树不为空，则左子树上所有节点的值均小于或等于它的根节点的值。
2. 若右子树不为空，则右子树上所有节点的值均大于或等于它的根节点的值。
3. 左、右子树也分别为二叉查找树。
4. 没有键值相等的节点。

复杂度：

算法	平均	平均
空间	O(n)	O(n)
搜索	O(log n)	O(n)
插入	O(log n)	O(n)
删除	O(log n)	O(n)

定义节点

class BinarySearchTree(object):
    def __init__(self, data, left=None, right=None, parent=None):
        self.data = data
        self.left = left
        self.right = right
        self.parent = parent

查找操作

在二叉查找树b中查找x的过程为：

1. 若b是空树，则搜索失败，
2. 否则： 若x等于b的根节点的数据域之值，则查找成功；
3. 否则： 若x小于b的根节点的数据域之值，则搜索左子树；
4. 否则：查找右子树。

插入操作

向一个二叉查找树b中插入一个节点s的算法，过程为：

1. 若b是空树，则将s所指节点作为根节点插入，
2. 否则： 若s->data等于b的根节点的数据域之值，则返回，
3. 否则：若s->data小于b的根节点的数据域之值，则把s所指节点插入到左子树中，
4. 否则： 把s所指节点插入到右子树中。（新插入节点总是叶子节点）

删除步骤

• 从 BST中删除节点比插入节点难度更大。因为删除一个非叶子节点，就必须选择其他节点来填补因删除节点所造成的树的断裂。如果不选择节点来填补这个断裂，那么就违背了BST 的性质要求。
• 删除节点算法的第一步是定位要被删除的节点，这可以使用前面介绍的查找算法，因此运行时间为O(log­2n)。接着应该选择合适的节点来代替删除节点的位置，它共有三种情况需要考虑。

情况 1：若被删除结点为叶子结点，即该节点的左子树和右子树均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。
情况 2：若被删除结点只有左子树或右子树，此时只要令左子树或右子树直接成为其双亲结点的左子树或右子树即可，作此修改也不破坏二叉查找树的特性。
情况 3：
若被删除结点的左子树和右子树均不空，如果被删除节点的右孩子没有左孩子，那么这个右孩子被用来替换被删除节点。因为被删除节点的右孩子都大于被删除节点左子树的所有节点，同时也大于或小于被删除节点的父节点，这同样取决于被删除节点是左孩子还是右孩子。因此，用右孩子来替换被删除节点，符合二叉查找树的性质。
如果被删除节点的右孩子有左孩子，就需要用被删除节点右孩子的左子树中的最下面的节点来替换它，就是说，我们用被删除节点的右子树中最小值的节点来替换。

遍历步骤

先序遍历，中序遍历，后序遍历

代码实现

class BinarySearchTree(object):
    def __init__(self, data, left=None, right=None, parent=None):
        self.data = data
        self.left = left
        self.right = right
        self.parent = parent
class BST(object):
    def __init__(self):
        self.root = None
        self.size = 0
    def lenght(self):
        return self.size
    def find(self, key):
        if self.root:
            result = self._find(key, self.root)
            if result:
                return result
            else:
                return None
        else:
            None
    def _find(self, key, node):
        if not node:
            return None
        elif node.data == key:
            return node
        elif key < node.data:
            return self._find(key, node.left)
        else:
            return self._find(key, node.right)
    def insert(self, key):
        node = BinarySearchTree(key)
        if not self.root:
            self.root = node
            self.size += 1
        else:
            currentNode = self.root
            while True:
                if key < currentNode.data:
                    if currentNode.left:
                        currentNode = currentNode.left
                    else:
                        currentNode.left = node
                        node.parent = currentNode
                        self.size += 1
                        break
                elif key > currentNode.data:
                    if currentNode.right:
                        currentNode = currentNode.right
                    else:
                        currentNode.right = node
                        node.parent = currentNode
                        self.size += 1
                        break
                else:
                    break
    def findMin(self):
        if self.root:
            return self._findMin(self.root)
        else:
            return None
    def findMax(self):
        if self.root:
            currentNode = self.root
            while currentNode.right:
                currentNode = currentNode.right
            return currentNode
        else:
            return None

    def _findMin(self, node):
        if node:
            currentNode = node
            while currentNode.left:
                currentNode = currentNode.left
            return currentNode
    def delete(self, key):
        if self.size > 1:
            nodeToDelete = self.find(key)
            if nodeToDelete:
                self._delete(nodeToDelete)
                self.size -= 1
            else:
                raise KeyError('Error, key not in tree')
        elif self.size == 1 and self.root.data == key:
            self.root = BinarySearchTree(None)
            self.size = 0
        else:
            raise KeyError('Error, key not in tree')
    def _delete(self, node):
        if not node.left and node.right: #node为树叶
            if node == node.parent.left: #node为父节点的左子树
                node.parent.left = None
            else:
                node.parent.right = None
        elif node.right and node.left: #node有两个儿子
            minNone = self._findMin(node.right)
            node.data = minNone.data
            self._delete(minNone)
        else: #node有一个儿子
            if node.left: #node有左儿子
                if node.parent and node.parent.left == node: #node为父节点的左子树
                    node.left.parent = node.parent
                    node.parent.left = node.left
                elif node.parent and node.parent.right == node: #node为父节点的右子树
                    node.left.parent = node.parent
                    node.parent.right = node.left
                else:  # node为根
                    self.root = node.left
                    node.left.parent = None
                    node.left = None
            else:
                if node.parent and node.parent.left == node:
                    node.right.parent = node.parent
                    node.parent.left = node.right
                elif node.parent and node.parent.right == node:
                    node.right.parent = node.parent
                    node.parent.right = node.right
                else:
                    self.root = node.right
                    node.right.parent = None
                    node.right = None
    def printTree(self):
        if self.size == 0:
            print("Empty Tree")
        else:
            self._printTree(self.root)
    def _printTree(self, node):
        if node: #中序遍历
            self._printTree(node.left)
            print(node.data)
            self._printTree(node.right)

转载：二叉搜索树的python实现

公众号：算法手记